Advanced Algorithms Laboratory (DT0547) - 2019/2020

Lecturer

Contact

Room 220
"Alan Turing" Building (Blocco 0)

{name}.{surname}@univaq.it
GPG Key: 0xCCEFF2F7

Time & Place

• Wednesdays, 8:30-11:30, Room A1.1, Coppito 0.
• Thursdays, 16:30-18:30, Room A1.1, Coppito 0.

Course program (subject to change)

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

Solutions¹: asteroid_mining.cpp, number_station.cpp