OVERVIEW

The course aims to introduce the student to the design and analysis of algorithms. Through the presentation of the main data structures and the algorithms relating to them, the student will develop an understanding of algorithms and the main techniques connected to them. A project created in C++ on Unreal Engine allows you to put some of the concepts proposed into practice.

AIMS AND CONTENT

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.

The course also introduces the fundamentals of programming in Unreal Engine for the development of graphic and interactive applications.

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.

Unreal Engine:

• Introduzione al framework
• Strutturazione di un'applicazione in Unreal Engine
• Elementi fondamentali 
• Esempio di applicazione: Tic-Tac-Toe

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;

TEACHERS AND EXAM BOARD

Exam Board

ARMANDO TACCHELLA (President)

MARCO MARATEA

MASSIMO NARIZZANO

ENRICO GIUNCHIGLIA (President Substitute)

LESSONS

LESSONS START

https://corsi.unige.it/8719/p/studenti-orario

Class schedule

The timetable for this course is available here: Portale EasyAcademy

EXAMS

EXAM DESCRIPTION

Take home project (10 points max), written test (20 points max)

Students with certification of Specific Learning Disabilities (SLD), disabilities, or other special educational needs must contact the instructor at the beginning of the course to agree on teaching and examination methods that, while respecting the course objectives, take into account individual learning styles and provide appropriate compensatory tools. It is reminded that the request for compensatory/dispensatory measures for exams must be sent to the course instructor, the School representative, and the “Settore servizi per l'inclusione degli studenti con disabilità e con DSA” office (dsa@unige.it) at least 10 working days before the test, as per the guidelines available at the link: https://unige.it/disabilita-dsa.

ASSESSMENT METHODS

Capability to frame solutions of computational problems through algorithms, and analyze the correctness and the performances of the solutions with analytical means.

Exam schedule