Algorithms

A.Y. 2018/2019
Lesson for
9
Max ECTS
89
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
The course consists of two parts: theory and laboratory. The first part is devoted to data structures and algorithms for classical problems. Our goal is to present the main methods for the design of algorithms and for their analysis, which includes an evaluation of the computation time and the memory space required by the procedures. The second part is devoted to the implementation in C of some data structures and algorithms studied in the first part.
The main goal of the course is the knowledge of basic methods for the design and the analysis of algorithms. We want to develop the ability of determining algorithmic solutions for a given problem together with the capability of implementing in C language the corresponding procedures and data structures.

Course structure and Syllabus

Active edition
Yes
Responsible
INF/01 - INFORMATICS - University credits: 9
Practicals: 44 hours
Lessons: 45 hours
Syllabus
Theory

Intuitive notion of problem and algorithm. Design and analysis of algorithms. Complexity of an algorithm, worst-case and average case analysis.
The RAM machine model. Syntax and semantics of RAM programs. Uniform and logarithmic cost criteria. Time and space complexity of RAM programs. High level (Algol-like) language.
Elementary data structures: arrays, lists, stacks, queues and corresponding implementation. Graphs, trees and their representations. Recursive procedures and corresponding iterative translation by a stack. Algorithms for visiting graphs and trees; depth-first search and breadth-first search.
Sorting algorithms and minimum number of comparisons. Insertionsort, heapsort, quicksort.
Abstract data structures. Binary search trees, B-trees. "Union-find" operations on partitions: algorithms based on forests with balancing and compression.
Divide and Conquer algorithms. Corresponding analysis of their time complexity (Master theorem): mergesort, binary search, algorithm for product of integers.
Dynamic Programming algorithms: transitive closure of graphs and (all pair) shortest paths.
Greedy algorithms. Algorithms for the minimum spanning tree (Kruskal, Prim) and for the shortest paths from a source (Dijkstra).

Laboratory

Asymptotic properties of sequences and sums. Main recurrence equations.
Elements of C language: program structure, primitive data types, expressions, control flow, lexical analysis, basic data structures (arrays, matrices, strings, records), recursive procedures and functions, pointers dynamic memory allocation.
Implementation of data structures and algorithms: sorting algorithms, lists, stacks and queues, graphs and trees, procedures for visiting graphs, balanced search trees, examples of dynamic programming and greedy algorithms.
Lesson period
Second semester
Lesson period
Second semester
Assessment methods
Esame
Assessment result
voto verbalizzato in trentesimi
Professor(s)
Reception:
By appointment
DI - Via Comelico 39/41