Toolbox
On this page you find background material for the topics we discussed in the sessions.
By default, we use python as a programming language, and
kattis
as an online judge.
0. Input-Output Essentials
We give an overview of how to interact with the kattis platform and briefly discuss some strategies to deal with large inputs.
1. Running Time and Basic Data Structures
We give a brief introduction into running time analysis along with a table of feasible running times for a 1 second time limit. We then discuss some fundamental data structures and the performance of their basic operations: lists (incl. applications of sorting), sets, doubly-ended queues, and heaps.
Practice problems: list sorting set deque heap
2. Brute Force
We consider several ways of enumerating all possibilities, which is feasible for small-enough inputs. We discuss nested loops for enumerating tuples of small dimensions, methods for enumerating all subsets and all permutations. We look at bitmasks as an efficient representation of small sets.
Practice problems: brute-force (all) nested-loops bitmask subset permutation
3. Introduction to Graphs
We give an introduction to the basic notions around graphs and directed graphs (digraphs) and discuss ways of representing them.
Practice problems: basic graph basic digraph