Algorithm Design Laboratory with Applications

Stefano Leucci
Academic Year 2024/2025

Schedule

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

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

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

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

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

The Split and List Technique, the 2-SAT problem

The Subset-Sum problem: definition and a dynamic programming algorithm. Pseudopolynomial-time algorithms. The split and list technique: Improving the trivial O*(2^n)-time algorithm for subset-sum to a O*(2^(n/2))-time algorithm. Techniques for generating all subsets sums of a set, a trivial O(n2^n) algorithm, a O(2^n) algorithm.

A split and list algorithm for the Knapsack problem.

The 1-in-3 Positive SAT problem: definition, improving the trivial O*(2^n)-time algorithm to a O*(2^(n/2))-time split and list algorithm.

The 2-SAT problem: the implication graph, strongly connected components, and topological sorting. Relation between strongly connected components and 2-SAT.

Material

Tarjan's algorithm for SCCs. Introduciton to the Boost Graph Library

Tarjan's algorithm for computing Strongly Connected Components, proof of correctness and analysis of its running time.

The Boost Graph Library: fundamentals, graph representations, vertex and edge descriptors, iterators, internal property maps, external property maps.

Algorithms in BGL: topological sorting, connected components, strongly connected components, named parameters, solving 2-SAT with BGL, single source distances (in DAGS, using Dijkstra algorithm, using Bellman-Ford algorithm), all to all distances (Floyd-Warshall algorithm), minimum spanning trees (using Kruskal algorithm, using Prim algorithm).

Visits in BGL: the BFS visitor, the DFS visitor.

Material

Applications of Network Flows

The maximum flow problem: definition, linear programming formulation, augmenting paths and residual graphs. Flow algorithms (without analysis): Ford-Fulkerson, Edmonds-Karp, and Push-Relabel. Handing multiple sources, vertex capacities, undirected graphs, and minimum capacities.

Network flow in BGL: graph representation, invoking Edmonds-Karp and Push-Relabel.

Flow applications: the minimum s-t cut problem and the max-flow min-cut theorem. Finding the maximum number of edge-disjoint paths, the circulation problem, the maximum bipartite matching problem and Kőnig's theorem, image segmentation.

Min-cost max-flow and applications. Minimum-cost bipartite matching. Min-cost max-flow in BGL: using the Cycle Canceling algorithm, and the Successive Shortest Paths algorithm.

Material

Laboratory Problems

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

References