Laboratory of Competitive Programming

  • c. 38104
  • Introduction to coding competitions
  • Python fundamentals
  • Data structures and common patterns
  • Introduction to Evolutionary Computing

The goal of the course is to study and learn how to solve algorithmic problems typically found in coding competitions. The focus is mainly on understanding how to use fundamental algorithms, data structures, and common approaches (or patterns) to produce solutions with low computational complexity. We will also gradually learn Python.

Starting from 2024, the course also provides an introduction to Evolutionary Computing by prof. Angelo Gargantini.

General info

  • Email
  • University e-Learning platform
    • Official communications
    • Study material (copy)
  • Office hours (for students)
    • Weekly on Wednesday, 10.30-11.30, Dalmine, Building B, room 3.05
    • It is appreciated to make an appointment by mail in advance
  • Timetable (2024)
    • Wednesday 8.30-10.30, lab Galvani, 1st floor
    • Friday 14.00-16.00, room B005
    • 40 hours of lesson

Unit 0

  • Course introduction slides
    • Program
    • Study material and official book
    • Exam and (optional) project
    • Weekly calendar

Unit 1

  • Computational complexity slides
    • Growth of functions
    • Big-Θ, Big-O, Big-Ω notation
    • Code examples

Unit 2

  • Choice of the programming language slides
    • Advantages and drawbacks
  • Python programming fundamentals - pt.1 slides
    • Data model
    • Name resolution
    • Containers - list vs tuple
    • Dynamic resizing
    • Range, enumerate and list comprehension
    • Functions
  • Python programming fundamentals - pt.2 slides
    • String
    • Containers - set vs dict
    • Zip, map and dictionary comprehension
    • Stdin and Stdout
  • Coding strategies slides
    • Sliding windows, two pointers, fast and slow pointers
  • Python programming practice, solutions

Unit 3

  • Sorting slides
    • Bubble sort, selection sort, insertion sort
    • Merge sort, quick sort, heap sort (max-heap), radix sort
    • Hybrid approaches
  • Python programming practice

Unit 4

  • Data structures
    • Linked list slides
      • append, get, set_at, delete_at, reverse, detect cycles
    • Queue and stack slides
      • push, pop, deque container
    • Heap slides
      • min-heap, max-heap, heapq module, priority queue
    • Binary tree slides
      • search, in-order, pre-order, post-order, reverse, lowest common ancestor, height, full tree
    • AVL tree slides
      • left and right rotations, balance factor, insert, delete
    • Graph slides
      • directed vs undirected, representations, bfs, dfs, acyclicity, shortest path, bridges
    • Trie slides
      • construction, key lookup, autocompletion
    • Disjoint-set or union-find slides
      • problem statement, union by rank, path compression
    • Sparse table slides
      • precomputation, range minimum queries
  • Python programming practice

Unit 5

  • Dynamic programming slides
    • Minimum edit distance, minimum number of coins, knapsack
  • Python programming practice

© 2023 Dario Facchinetti