A Glimpse into Algorithms (minicourse)

Revisions

• Version 1, Workshop (2020): ca. 2 hours session, online. Russian (presentation) / English (materials),
• Version 2, Minicourse (2021): four sessions, one hour each, online. Russian and English (materials in English only).
• Version 3, Minicourse (2022): four sessions, one hour each, online. Russian (materials in English only).

Background

This is an attempt to think about the matter from the “experimental” perspective. For example, when discussing the asymptotic runtime, people want to know that “this is slow” and “this is fast”, but we use a definition that allows to hide an arbitrary constant in it 🤷! This is usually pretty practical, just takes time to sink in. Why don’t we just measure “runtime” of an algorithm in seconds, with, you know, time function? So, my purpose was to pick specific examples (in Python) and show why a simple stopwatch won’t work, and try to derive better ways of measuring runtime. I found that looking at an actual code of a simple algorithm did help the discussion of more general concepts.

Prerequisites and learning objectives

The course did not assume any serious background in CS, but it was designed with a specific student in mind. Someone who is not afraid of the code, but is still lost in how to analyze it and, ultimately, how to design it. The purpose was to give an intuitive understanding of:

• the fact that algorithms and data structures can and should be analyzed in a systematic, scientific manner;
• what is correctness, why and how to think about it (testing the code, finding counterexamples, proving correctness);
• what are some key approaches to discussing runtime; what is O(·) notation;
• what are “complexity classes”;
• the fact that there are different approaches to designing an algorithm.
• what is Dynamic Programming and how does global sequence alignment works (conceptually),
• why data structures are important (even if you don’t want to be a software engineer).

It seems impossible to lay a solid foundation in just four sessions, but I do hope that after the course the students were ready to pick up a good book or proceed with a course discussing these concepts in proper detail, and well equipped to succeed in such further learning.

Course organization

The course was organized into three blocks (the first one taking two hours):

• Discussion of the concepts of correctness, time, and space properties, having sorting algorithms as the working example. We also discussed some patterns of designing algorithms: divide and conquer, greedy, etc.
• A concept of dynamic programming and a specific example of such algorithm. (Due to the School’s emphasis on Biology, folks were interested in sequence alignment algorithms.)
• Introduction of data structures, very briefly comparing runtimes for different operations over arrays, linked lists, and dictionaries¹

See the full course outline for details.

Technical details

The course was delivered online. The central idea required working with the code most of the time, so I presented the material directly from Jupyter notebook with RISE plugin (which produced Reveal.js slides). This allowed me to run code interactively, change parameters, comment/uncomment lines, and observe what is going on.

The built-in “chalkboard” feature also proved to be very convenient: for writing on top of the slides or on a clean blackboard (using a simple drawing tablet).