Algorithms and Data Structures (2007/2008)

Course partially running

Teaching is organised as follows:
Unit Credits Academic sector Period Academic staff
Teoria 8 INF/01-INFORMATICS 1° Q, 2° Q Roberto Segala
Laboratorio 2 INF/01-INFORMATICS 2° Q Isabella Mastroeni
Roberto Posenato

Learning outcomes

Module: Teoria
-------
The course covers basic concepts for the formulation and algorithmic solution of complex problems. Problems are formulated and solved in terms of abstract mathematical structures (lists, queues, graphs, ...). Algorithms are evaluated and compared based on the quantities of the requested resources. The course also focuses on the role of data structures in the formulation and evaluation of new algorithms.


Module: Laboratorio
-------

Syllabus

Module: Teoria
-------
The course consists of 64 hours of front lectures, includiong 20 hours of recitation sections where studens must solve guided problems.

Specific arguments include

Complexity: asymptotic notation, resolution ofrecurrence equations, amortized analysis.

Selection and sorting: insertion sort, merge sort, heap sort, quick sort, randomized quick sort. Complexity of sorting algorithms, lower bounds on comparison based algorithms. Sorting in linear time, counting sort, radix sort, bucket sort. Selection, minimum, maximum, randomized select, linear time select.

Data structures: queues, stacks, lists, heaps, binary search trees, RB-trees, binomial heaps, disjoint sets. Extension of a data structure.

Graphs: definition and representation, breadth first search, depth first search, topological sorting, connected components, minimum spanning trees (Prim and Kruskal), shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson), maximum flow (Ford-Fulkerson, Karp), maximal matching on bipartite graphs.


Module: Laboratorio
-------

Assessment methods and criteria

Module: Teoria
-------
The exam for the "theory" module consists of a written test of two hours containing three problems of increasing difficulty that evaluate knowledge as well as capacity of reasoning. Lhe written test is passed with a grade of at least 18/30. The student may bring a sheet of paper, A4 format, hand-written on both sides. On each side the student must write name and id number.


Module: Laboratorio
-------

Reference books
Author Title Publisher Year ISBN Note
Giovanni Pighizzini, Mauro Ferrari Dai fondamenti agli oggetti. Corso di programmazione JAVA (Edizione 3) Pearson Addison-Wesley 2008 978 88 7192 448 9

Studying