# Algorithm Design Laboratory with Applications

## Schedule

- Monday 8:30 - 11:30. Room A1.2 C1.16.
- Thursday 14:30 - 16:30. Room A1.2.

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

## News

The lecture scheduled for May 27, 2024 is cancelled.## Exam Dates

- June 12, 2024 at 14:00. Room A1.3. Register by June 07, 2024. The oral part of the exam will take place on June 13 from 15:30. Results.
- June 26, 2024 at 14:00. Digital class. Register by June 21, 2024. The oral part of the exam will take place on July 2 from 15:00. Results.
- July 10, 2024 at 14:00. Room A1.3. Register by July 05, 2024. Results.
- September 11, 2024 at 14:00. Room TBA. Register by September 06, 2024.

## 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. Example 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

- 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) algorithm and a O(n log n) algorithm.

#### Material

- Section 5.5 of [KT], where the divide and conquer technique is applied to integer multiplication.
- Section 6.1 of [KT], where memoization is applied to weighted interval scheduling.
- Exercise 17 in Chapter 6 of [KT] asks to solve the longest increasing subsequence problem.
- Exercises 15.4-5 and 15.4-6 of [CLRS] ask to solve the longest increasing subsequence problem in O(n^2) and O(n log n) time, respectively.
- Section 2 of M. L. Fredman,
*On computing the length of longest increasing subsequences*. - Slides: divide and conquer, memoization, dynamic programming.

### 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.

#### 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].
- Slides: Independent Set and Edit Distance.

### Even More Dynamic Programming and the Split and List Technique

The Subset-Sum problem: definition and a dynamic programming algorithm. Pseudopolynomial-time algorithms.

See Chapter 3.8 of [E] and Chapter 6.4 of [KT].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 (see also Chapter 17.1 of [CLRS]).

The Knapsack problem: a dynamic programming algorithm with polynomial running time in the number of items and in the maximum weight (see Chapter 6.4 of [KT]). A dynamic programming algorithm with polynomial running time in the number of items and in the optimal value. A split and list algorithm (see also Chapter 9.1 of [F]).

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. See Chapter 9.1 of [F].

#### Material

- Chapter 3.8 of [E].
- Chapter 6.4 of [KT].
- Chapter 17.1 of [CLRS].
- Chapter 9.1 of [F].
- Slides: Subset-Sum and 1-in-3 Positive SAT.
- Slides: Knapsack.

### The 2-SAT Problem: Limited Backtracking and Strongly Connected Components

The 2-SAT problem: the algorithm of Even, Itai, and Shamir and its analysis (see Section 2 of [1]).

2SAT and Strongly Connected Components: The implication graph, strongly connected components, topological sorting. Relation between strongly connected components and 2SAT (with proof).

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

#### Material

- Section 2 of S. Even, A. Itai, A. Shamir,
*On the complexity of time table and multi-commodity flow problems*. - See Chapter 12.5.2 of [DFI] or Chapter 6 of [E].
- Slides: Solving 2-SAT via limited backtracking.
- Slides: Solving 2-SAT via strongly connected components and Tarjan's algorithm.

### Introduciton to 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

- Slides: the Boost Graph Library.
- Official documentation of the Boost Graph Library.
- Useful code snippets for the BGL.

### 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.

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

- Chapters 7.1 and 7.2 of [KT].
- Chapter 21 of [CLRS].
- Chapter 11 of [E] for the discussed applications and more.
- The interested students can find a description of the flow algorithms in Chapter 10 of [E] and in Chapters F and G of the "Extended Dance Remix" of [E].
- Slides: network flows.
- Useful code snippets for flow algorithms using the BGL.

### Oracles for Lowest Common Acestors and Range Minimum Queries

Designing an oracle for Lowest Common Ancestor (LCA) queries: problem definition, trivial solutions, Euler tours and relation to oracles for Range Minimum queries (RMQ).

Designing an oracle for RMQ: problem definition, trivial solutions, the "Sparse Table" oracle, improving the sparse table oracle using blocks. The ±1 RMQ problem. An oracle with optimal size and query time for ±1 RMQ using blocks and block types.

Reducing the problem of designing an oracle for general RMQ to the problem of designing an oracle for LCA queries. Cartesian trees: definition, constricting a Cartesian tree in linear time. Relation between LCA queries in Cartesian trees and general RMQ. An oracle with optimal size and query time for general RMQ.

#### Material

- M. A. Bender and M. Farach-Colton,
*The LCA Problem Revisited*. - Slides: Oracles for LCA and RMQ queries.

### Oracles for Level Ancestor Queries

Designing an oracle for Level Ancestor queries, problem definition and trivial solutions. A first non-trivial oracle using jump pointers.

The long path decomposition of a tree: an oracle using the long path decomposition, tight analysis of the number of paths of the decomposition encountered in a root-to-leaf path and relation with the oracle's query time. Extending the paths of the decomposition into ladders, combining ladders with jump pointers.

The micro-macro tree decomposition, handling the macro-tree, handling micro-trees and bounding the number of distinct micro-tree types, combining the previous oracles into a new oracle with optimal space, preprocessing time, and query time.

#### Material

- M. A. Bender and M. Farach-Colton,
*The Level Ancestor Problem Simplified*. - Slides: Oracles for level ancestor queries.

### Range Trees

A data structure for orthogonal range searching: Range trees. Problem definition. Solution for the 1-dimensional case using arrays and binary search. Solution for the 1-dimensional case using binary trees. Solution for the 2-dimensional case. Reducing the construction time. Solution for the D-dimensional case for D>2.

Fractional cascading: problem definition, naive solution. Two ideas: cross-linking and fractional cascading. Using cross-linking to improve the query time for 2-dimensional range trees. Extension to D>2.

#### Material

- Slides: Range Trees.
- Here is the recording of an excellent lecture on range trees by Erik Demaine (up to minute 40:00).

### van Emde Boas trees

The Dynamic Predecessor problem: definition and a trivial solutions. Speeding up naive queries with clusters and summaries.

Proto-van Emde Boas trees. Bounding the space usage. A first implementation of Find, Insert, and Successor.

Tge actual van Emde Boas trees: a faster implementation of Find, Insert, and Successor. Handling deletions. Reducing the space usage to O(n) (sketch of the ideas). A sample application (packet routing).

#### Material

- Chapter 20 of [CLRS].
- Slides: van Emde Boas trees.

## Laboratory Problems

**Asteroid mining:**statement, test-cases.**Number station:**statement, test-cases.**A massive bookwork:**statement, test-cases.**Mountain trip:**statement, test-cases.**Travelling salesman:**statement, test-cases.**Postal service:**statement, test-cases.**Lazy hikers:**statement, test-cases.**Two trees:**statement, test-cases.**HDMI cables:**statement, test-cases.**Tunnel:**statement, test-cases.**Souvenirs:**statement, test-cases.**Omicron persei 8:**statement, test-cases.**Bookshelf:**statement, test-cases.**Book printing:**statement, test-cases.**Candies:**statement, test-cases.**Deep sea research:**statement, test-cases.**Metro:**statement, test-cases.**Sliding token:**statement, test-cases.**Planet express:**statement, test-cases.**Che$$board:**statement, test-cases.**Switches:**statement, test-cases.**Buffering:**statement, test-cases.**Catch the robber:**statement, test-cases.**Gift:**statement, test-cases.**Water treatment plant:**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.