LEARNING OUTCOMES

The course introduces the main strategies to design algorithms and the tools to assess their correctness and performances. The goal is to develop the student's capabiliry to formalize and solve problems algorithmically. Also, the student should gain the capability of analising and evaluating alternative solutions.

AIMS AND LEARNING OUTCOMES

The course introduces the main strategies of algorithm design:

• Brute Force: solving problems starting from their formal definition
• Divide and Conquer: approaching problems by dividing them up into smaller ones (usually of the same size) and the recombining partial solutions
• Diminish and Conquer: reduce the problem size iteratively (of a constant, of a constant factor, of a variable factor)
• Transform and Conquer: approaching problems by reformulating them in order to simplify their solution
• Space-Time Tradeoff: improving on time efficiency by utilizing memory overheads
• Greedy Algorithms: solving combinatorial optimization problems by adopting greedy strategies, i.e., locally optimal choices which reveal to be optimal also in the global sense.

Overall, the expected outcome is to obtain a good knowlege of the main algorithms, at least one per family. The result will be the ability to solve computational problems with an algorithms approach and analyze the complexity through analytical or empirical means.

PREREQUISITES

A good knowledge of at least one programming language of the family C/C++/Java is required.

Knowledge of combinatorics, basic algebra and theoretical computer science are useful to better understand the topics covered in the course.

TEACHING METHODS

Lectures and computer labs, possibly delivered online.

SYLLABUS/CONTENT

Design and Analysis of Algorithms

Introduction: definition of algorithm; fundamental aspects of problem solving through algorithms; problem types and solution strategies; specification of algorithms through flow charts and pseudo-code; syntax and semantics of pseudo-code.

Fundamental data structures; linear structures (array, strings, stacks, queuses and listsl); graphs (definitions and data structures) ; trees (definitions and data structures) ; sets, dictionaries and maps (fundamentals).

Basic elements: algorithms efficiency, computational resources and RAM model; asymptotic notation  (properties and fundamental classes); analysis of algorithms (worst case, best case, average case); lower bound and optimality; amortized efficiency.

"Brute Force" Strategy: methodology and examples of analysis for non-recursive algorithms (finding maximum, element uniqueness, matrix multiplication). Elementary sorting algorithms on vectors (Selection Sort). Sequential search on vectors; sets, dictionaries and maps with dynamical arrays and linked lists; string search (string matching).

"Divide and conquer" Strategy: methodology and examples of analysis for recursive algorithms; Master Theorem. Sorting algorithms (Mergesort and Quicksort); lower bound for sorting algorithms based on comparisons; binary trees (definition, computing the height, visiting trees); syntax analysis in formal languages (language, context free grammars); recursive top-down parsing.

"Decrease and conquer": sorting algorithms on vectors (Insertion Sort); graph visits (depth first and breadth first); topological sort; finding strongly connected components on directed graphs; binary search in vectors; compute powers for integers and matrices; binary search trees.

"Transform and conquer": heap data structures; using heap to sort vectors and handle priority queues; experimental compariso between O(nlogn) sorting algorithms; Horner's method to compute polynomials; disjoint sets and union-find techniques; balanced search trees: 2-3 trees and LLRB trees; tries.

 "Space-Time trade-off": linear time sorting (Counting Sort); direct access tables, hash tables (separate chaining); hash functions.

 "Greedy Algorithms" : Prim and Kruskal algorithms to compute minimum spanning trees; Dijkstra algorithms to compute minimum paths; Huffman codes for data compression.

Object Oriented Programming (with references to Core Java I e II)

Introduction and reprise of objects and classes (Core Java I - Cap. 4) and inheritance (Core Java  I - Cap. 5), "legacy" library for reading and writing text files.

Interfaces, lambda expressions and inner classes (Core Java I - Cap. 6); strings and memory handling, measuring performances.

Object oriented programming: UML (class diagram, sequence diagram, state diagram);

Exceptions and logging (Core Java I - Cap. 7), releasing Java applications (Core Java I - Cap. 13)

Generic programming (Core Java I - Cap. 8), Java collection framework (Core Java I - Cap. 9)

Design Patterns (creational, structural and behavioral); most common patterns (Factory Method, Iterator, Composite, Decorator, Interpreter, Visitor, Observer)

Streams (Core Java II - Cap. 1) and I/O (Core Java II - Cap. 2)

RECOMMENDED READING/BIBLIOGRAPHY

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein ‐ Introduzione agli algoritmi e strutture dati ‐ 3a Edizione ‐ McGraw ‐ Hill;

R. Sedgewick ‐ Algorithms ‐ 4th edition ‐  Addison Wesley

A. Levitin ‐ Introduction to The Design and Analysis of Algorithms ‐ 2nd edition ‐ Addison ‐ Wesley;

S. Skiena ‐ The Algorithm Design Manual ‐ 2nd edition – Springer;

Cay Horstmann - Core Java (Vol. 1 e 2) - Prentice Hall