Algorithm Design Laboratory with Applications

Stefano Leucci
Academic Year 2024/2025

Schedule

• Monday 10:30 - 13:30. Room A1.2.
• Thursday 9:30 - 11:30. Room A1.2.

Office hours: Thursday 14:30 - 16:30. Please send me an email or ask before/after the lectures.

Lectures and Material

Introduction and Prefix Sums

Course overview.
Introduction to laboratory exercises: exercises format, writing, compiling, evaluating, and debugging a solution. Programming tips, assertions.
The STL library: overview, basic types, containers (arrays, vectors, deques, queues, stacks, (muti-)sets, priority queues), iterators, algorithms: (heaps and sorting, linear search, binary search, deleting and replacing elements).
The prefix sums technique. Counting the number of contiguous subsequences with even total sum: cubic-, quadratic-, and linear-time solutions.

Material

• Slides: introduction to laboratory excercises.
• Slides: the STL library.
• Slides: prefix_sums.

Sorting, Binary Searching, and Sliding Window

Sorting and binary searching with predicates. Computing good upper bounds using exponential search.
The sliding window technique. Examples with cubic-, quadratic-, almost linear-, and linear-time solutions.

Material

• Slides: sorting, binary search, and exponential search.
• Slides: sliding_window.

Greedy algorithms

Greedy algorithms. Interval scheduling: problem definition, the earliest finish time algorithm, proof of correctness (greedy stays ahead).
Interval partitioning: problem definition, greedy algorithm, proof of correctness (using structural properties).
Scheduling jobs with deadlines to minimize lateness. The Earliest Deadline First algorithm. Proof of correctness through an exchange argument.

Material

• Sections 4.1 and 4.2 of [KT].
• Section 6.1 of [CLRS].
• Slides: greedy algorithms.

Laboratory Problems

The online judge is accessible at https://judge.stefanoleucci.com.

• Asteroid mining: statement, test-cases.
• Number station: statement, test-cases.
• A massive bookwork: statement, test-cases.
• Travelling salesman: statement, test-cases.
• Mountain trip: statement, test-cases.
• Postal service: statement, test-cases.

References

• [CLRS]: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (3rd Edition). MIT Press. ISBN 978-0-262-53305-8.
• [KT]: Jon Kleinberg, Éva Tardos. Algorithm Design. Pearson. ISBN 0-321-29535-8.
• [DFI] Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano. Algoritmi e Strutture Dati (seconda edizione). McGraw-Hill. ISBN: 978-8838664687.
• [E]: Jeff Erickson. Algorithms. 978-1-792-64483-2. Freely available under the Creative Commons Attribution 4.0 International License at the book website.
• [F]: Fedor V. Fomin, Dieter Kratsch. Exact Exponential Algorithms. Springer. ISBN 978-3-642-16533-7. Freely available for personal use here.