Algorithm Design Laboratory with Applications

Stefano Leucci
Academic Year 2025/2026

Schedule

• Monday 8:30 - 11:30. Room A1.2.
• Thursday 11:30 - 13:30. Room A0.4.

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.
• Documentation of the Standard Template Library.
• 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.

Divide and Conquer, Memoization, and Dynamic Programming

The divide and conquer technique and the polynomial multiplication problem.
Recursion and memoization: computing Fibonacci numbers recursively in linear-time.
Introduction to dynamic programming. A trivial example: computing Fibonacci numbers iteratively. The Longest Increasing Subsequence problem: a O(n^2)-time algorithm. The segmented least squares problem: a dynamic programming algorithm running in time O(n^2).

Material

• Section 5.5 of [KT], where the divide and conquer technique is applied to integer multiplication.
• Section 3.1 of [E] discusses memoization and dynamic programming and applies these techniques to the problem of computing the n-th Fibonacci number.
• Sections 6.1 and 6.2 of [KT], where memoization and dynamic programming are applied to the weighted interval scheduling problem.
• Sections 6.3 of [KT], where dynamic programming is used to solve the segmented least squares problem in time O(n^3).
• Section 3.7 of [E] shows how to solve the longest increasing subsequnce problem in O(n^2) time using dynamic programming.
• Slides: divide and conquer, memoization, dynamic programming.
• Slides: segmented least squares.

More Dynamic Programming

Maximum-weight independent set on paths (linear-time algorithm), Maximum-weight independent set on trees (linear-time algorithm), Maximum weight independent set on trees with cardinality constraints. Counting the number of ways to distribute budget with stars and bars. Dynamic programming algorithm to optimally distribute budget.

The minimum edit distance problem: definition, quadratic algorithm, techniques for reconstructing optimal solutions from the dynamic programming table.

The Knapsack problem: a dynamic programming algorithm with polynomial running time in the number of items and in the maximum weight. A dynamic programming algorithm with polynomial running time in the number of items and in the optimal value.

Material

• Exercise 1 and Solved Exercise 1 in Chapter 6 of [KT].
• Excercise 15-6 of [CLRS] and section "Maximum-Weight Independent Set on Trees" in Chapter 10.2 of [KT].
• Chapter 3.7 of [E].
• Chapter 6.4 of [KT]
• Slides: Independent Set and Edit Distance.
• Slides: Knapsack.

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.
• Lazy hikers: statement, test-cases.
• HDMI cables: statement, test-cases.
• Two trees: statement, test-cases.
• Tunnel: statement, test-cases.
• Souvenirs: statement, test-cases.
• Deep sea research: 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.