Giving a talk about algorithms

Below is some advice on how to prepare a talk/lecture in a seminar on algorithms.

Find out how different parts of the material relate to each other. Ask yourself questions such as:

• What would be a straightforward algorithm for the problem?
• What would be the main bottleneck or shortcoming of such an algorithm?
• What is the main trick used in the paper to solve that bottleneck? Can you summarize it in a “catch line” of a few words?
• What assumptions do the authors make? Are these assumptions reasonable?
• Which part of the algorithm in the paper dominates the running time?
• Do upper and lower bounds match, or could the problem possibly be solved faster or better?
• What are the obvious questions/doubts about correctness and/or running time that arise while reading the paper, and have you found an answer to these questions?
• Do experimental data support the conclusions of the paper? Could other experiments have provided more compelling data?
• How does the material relate to other papers that you studied recently?
• What is the most interesting or surprising part of the paper and what is only a variation or a standard trick?
• Why are the ideas and the results of the paper interesting? Think of examples or applications that interest you.

Do not start making slides yet!

First decide what is the main message you want to get across. This is probably not that a certain problem can be solved in a certain amount of time: for that message you would not need to give a whole lecture. More likely you want to convince your audience of the effectiveness of a certain algorithmic design trick or a certain proof technique.

Now find out how to organize your talk around that message. Your talk will include at least:

1. Introduction of the algorithmic problem (definition and motivation).
   • First get the audience interested: give an example that illustrates:
     1. why the problem is interesting (relevant for theory or practice);
     2. why the problem is non-trivial to solve.
   • Then define the problem more precisely and formally.
2. Exposition and explanation of the solution.
   What building blocks do you need, and in what order will you present them?
   • First give an outline of the solution.
   • Then fill in the details of the building blocks.
     You will not have time to explain everything. Which proofs/details are relevant to your main message, and which proofs/details can you skip? Your main responsibility as a speaker is to make this selection. To be able to do so, you will need to have figured out many details yourself, you will need to understand the computations in the paper to see what precisely makes it all work etc. Now decide what to present to the audience, and what to skip or to tell only when somebody asks a question.
   • Then present/summarize the complete solution.
3. Analysis and evaluation of the solution.
   • Analyse the solution.
   • Compare the solution to other solutions, lower bounds etc.
   • (Re)state your main message.

The order given above is not strict: take it as a starting point. Now check what is the main message you want to get across to your audience. How do you make sure they get the point? If you follow the order given above strictly and give your talk in such a way that the main message becomes clear only at the end of the talk, then there is a big risk. By that time the audience is in dire need of coffee and you may be running out of the time.

As an alternative, consider going through the above sequence in several cycles: the first time informally, sketchy, skipping lots of things, but including the main points you want to make. Then adding more precision, more detail, more understanding in one or two more cycles—each time focusing on different aspects but always repeating the main points.

In any case do not try to stuff too much content in your talk. Rather than trying to explain a lot of things in a hurry, it is better to explain a few things clearly and at ease with lots of examples. Think of examples you can use to illustrate your talk.

Decide what visual aids you want to use. The options are usually computer presentations (made, for example, with IPE or PowerPoint), writing/drawing on the blackboard, physical models, and hand-outs.

Main advantages: typewritten and therefore easy to read, good for animations, and if need arises, you can always return to previous “slides”.

• Don't write too much.
  The text should only serve as an aid in understanding your talk, not the other way round. Write brief phrases, no full sentences. Use lay-out to link sentences together, rather than conjunctions: phrases linked by “and” or “or” can often be put in a vertical list of “bulleted” items; use arrows for “so”, “therefore” etc. Avoid items/paragraphs of more than two lines.

• Keep formulas simple.
  Leave out trivial details such as the bounds of the index in a summation, rounding operators etc. Only include what you will actually explain to your audience.
• Keep code simple, at most six lines.
  In a presentation, pseudocode can be used to clarify the structure of algorithms, but not to clarify the details of algorithms. Code in books often includes details such as trivial initializations, boundary cases etc. Leave out such details on slides. Use pseudocode, no real code. Only include what you will actually explain to your audience step by step. Summarize blocks of code into one line (a single statement or a description in English), until the full code is three to six lines long. Use the same font size as for normal slide text.
• Prepare lots of figures and examples rather than text.
• Never assume that the audience will be able to remember what was on the previous “slide”.
  For example, text and the illustrations to go with it should be put next to each other, not on separate slides. If you want to compare two algorithms, find a way to summarize them very succinctly so that both of them fit on the screen together and can still be read from the back of the room.
• Introduce all necessary concepts, definitions and notation clearly when first needed.
  Don't forget to define n!
• Make definitions, examples etc. available to your audience whenever you refer to them.
  Do not just introduce them once. Recall them at least verbally the second and third time you use them, and preferably also visually. Figure out if you can use the blackboard (or an overhead projector) to write down some definitions etc. that are used throughout the talk, and/or reserve a corner of the screen for basic definitions and leave them there throughout the talk.
• Use meaningful names for variables and parameters.
  Avoid variables with one-letter names, unless their use is standard.

Some advice on design:

• The default settings of PowerPoint are not so good for computer science talks, consider using these slides as a template.
• Use a font with uniform stroke width (for example Arial or Helvetica), size approximately 24 pt.
  Smaller text is fine in figures etc. but do not fill the full width of the slide with it.
• Associate phrases and variables in the text with parts of figures by giving them matching colours.
  But projection quality is usually not as good as a laptop screen, so:
  • Make sure the colours are redundant.
  • Do not assume that very light colours can be distinguished from white.
  • Make coloured dots, lines and text big/thick/bold so that their colours can be distinguished from the back of the room.
    The audience may be able to spot a dot of just a few pixels, but for the audience to see clearly what colour the dot is, it needs to be a lot bigger, especially when the projection quality is bad.
• The following things are useless for the audience and can therefore be omitted:
  • University logo (there is always a better use for the precious screen space)
  • Slide titles (no harm in including them, but the audience does not read them)
  • Talk outline slide (boring and a waste of time)
  • A final slide saying nothing but “thank you” or “questions?” (when you finish, leave a slide on with something for the audience to remember or to think about)

Main advantages: lots of space (so you can keep definitions and algorithms on the blackboard next to extensive illustrations); when you write or draw something on the blackboard, you direct the attention of your audience to exactly the right spot; the writing may keep you from going too fast for your audience.

Beware: preparing a blackboard talk takes as much time as preparing a computer presentation!

• You will run out of blackboard space. So plan (sketch) and practice how to use the space on the board: what will be on the board where and when.
• Plan and practice how to construct your examples. Also plan when to write things down: you may be able to save time by drawing the initial states of examples on the blackboard before the lecture or in the break.
• Make sketches and notes to use during the presentation.
• See under computer presentations for more advice.

Main advantages: they can be truly three-dimensional, and the audience will remember!

• Make sure everybody in the audience will be able to see what you are doing.

Not an alternative for scarce space on the projection screen! The audience cannot study a hand-out and listen to you at the same time.

Make notes for yourself to use while giving your talk, but do not write your talk out word by word!
If you can answer questions and discuss the material with your fellow-students in English, then you can also give a talk in English without preparing it word by word. Don't be afraid of making errors while speaking: a speaker who talks to his audience and formulates freely with errors is still easier to understand than one who reads flawless English from paper in one go!

Practice your talk. Do this early (you can already practice with rough paper sketches of your slides) because you may find that your talk needs to be changed substantially. While practicing:

• Look at the screen (or your sketches) as little as possible.
  When you give the talk, you will have to talk to your audience. You should not look down to your prints or your computer or back to the projection screen too often. So you will have to know what is on each slide without having to look at it.
• Make notes of what you forgot to say.
• Write down the time at several points in your talk.
  You can use the timings during the real presentation to check if you are going faster or slower than planned, so that you can decide to include or skip certain parts of your talk.
• Go slow at animations, formulas, pseudocode and charts!
  Explain to the (imaginary) audience what they see—all of it!

• Come to the lecture room in time
  Make sure all necessary equipment is there and works properly (projector, chalk or markers for the board, laser (or other) pointer).
• Greet your audience
  Do not put any essential information in your first two sentences. Your audience needs some time to change their mind set from chatting about life to listening carefully.
• Talk to your audience
  Look into the room (not at the blackboard). Pick a person or a point somewhat in the back of the room and talk in that direction. This also helps you to speak loud enough. Frequently pick another person, so that nobody feels singled out or ignored.
• Give your audience time to watch the show
  Especially if you have powerpoint animations etc., make sure you don't go too fast: give your audience time to discover all the nice things you put in there!
• Stop in time, skip things if necessary.
  If there is no clock in sight, do not hesitate to occasionally ask someone in the audience how much time you have left. If you are running out of time:
  • Never speed up: thus you would lose your audience and you could just as well stop talking.
  • Do not let your talk run late: the audience will start thinking about coffee or wherever they need to go next, instead of listening to you.
  • Do not tell the audience you have a timing problem: same effect as speeding up and running late.

If you are short of time, skip things, finish with your main message, and finish on time.

Any comments on this text are welcome, please send them to Herman Haverkort.