Laboratory of Competitive Programming

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

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.

General info

• Email
  • dario.facchinetti@unibg.it
• University e-Learning platform
  • Official communications
  • Exam results
  • Study material (copy)
• Office hours (for students)
  • Weekly on Tuesday, 16.00-17.00, Dalmine, Building B, room 3.05
  • It is appreciated to make an appointment by mail in advance
• Timetable
  • Tuesday 14.00-16.00, room B003
  • Friday 10.30-12.30, room A104

Unit 1

• Course introduction slides
  • Program
  • Study material and official book
  • Exam and (optional) project
  • Weekly calendar
• 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, practice
  • Data model
  • Name resolution
  • Containers - list vs tuple
  • Dynamic resizing
  • Range, enumerate and list comprehension
  • Functions
• Python programming fundamentals - pt.2 slides, practice
  • String
  • Containers - set vs dict
  • Zip, map and dictionary comprehension
  • Stdin and Stdout

Unit 3

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

Unit 4

• Coding strategies slides, practice
  • Sliding windows, two pointers, fast and slow pointers
• Data structures
  • Linked list slides, practice
    • reverse list, detect cycles
  • Queue and stack slides, practice
    • push, pop, deque
  • Heap slides, practice
    • min-heap, max-heap, heapq, priority queue
  • Binary tree slides, practice
    • insert, search, in-order, pre-order, post-order, reverse tree, lowest common ancestor
  • AVL tree slides, practice
    • rotate left and right, insert, delete
  • Graph slides, practice
    • directed vs undirected, representations, acyclicity, shortest path, bridges
  • Trie slides, practice
    • construction, key lookup, autocompletion
  • Disjoint-set or union-find slides, practice
    • problem statement, union by rank, path compression
  • Sparse table slides, practice
    • range minimum queries
  • LRU cache slides, practice
    • get, put, functools

Unit 5

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