Introduzione

Basic notions: definition of algorithm, how to read and write pseudocode, asymptotic analysis, definition of the RAM model. Chapters 2.1, 2.2 and 3.2 of Cormen's book.

Sorting and co: Insertion sort, Merge sort, Heaps and priority queues, Heap sort, Quick sort, Lower bound on sorting, Counting sort, Radix sort. Chapters 2.2, 2.3.1, 6, 7, 8.1, 8.2 and 8.3 of Cormen's book.

Binary search trees: definition, search, insertions, deletions. BST sort (inorder tree walk) and comparison with Quick sort. Chapters 12.1, 12.2, 12.3 and Problem 12-3 of Cormen's book.

Unweighted graphs: definition, representations of graphs, breadth-first search, shortest paths in unweighted graphs, depth-first search, edge classification, cycle detection, topological sort. Chapters 22.1, 22.2, 22.3 and 22.4 of Cormen's book.

Weighted graphs: definition. Single-source shortest paths (SSSP) problem: general scheme, edge relaxation, optimal substructure of shortest paths, topological-sort-based algorithm for SSSP on DAGS, Bellman-Ford algorithm for SSSP, Dijkstra's algorithm for SSSP. All-pairs shortes paths: Floyd-Warshall algorithm. Chapters 24.0, 24.1, 24.2, 24.3, 24.5 and 25.2 of Cormen's book.