Advanced Algorithms Laboratory (DT0547) - 2019/2020


Stefano Leucci


Room 220
"Alan Turing" Building (Blocco 0)


Time & Place

First lecture: February 26, 2020.
Office hours: Wednesdays, 10:30-12:30 upon prior agreement by email.

Course program (subject to change)

Coming soon.

Lectures & Material

February 26

Course overview.
Intruduction 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, maps, priority queues), iterators, some algorithms (heaps and sorting).

Material: Introduction to laboratory excercises, The STL library (1st part), STL library documentation.

February 27

The STL library (cont.): sorting, permutations, values queries, transformations, the reduce operation, linear search, binary search, operation on sets, copying collections, initializing collections, deleting and replacing elements.
The prefix sums technique. Conting the number of contiguous subsequence with even total sum: cubic-, quadratic-, and linear-time solutions.
Sorting and binary searching with predicates. Computing good upper bounds using exponential search.

Material: The STL library (2nd part), The prefix sums technique, Binary search, exponential search.

March 4

Laboratory. Problem Set 1, Test cases for "asteroid mining", Test cases for "number station".

Solutions1: asteroid_mining.cpp, number_station.cpp

1As requested, I have provided some reference solutions. However, please note that: (i) the code is not commented, and (ii) the proof of correctness and the analysis of the computational complexity of the implemented algorithms are missing (and have been discussed in class).