Algorithms (2010/2011)



Course code
4S02709
Credits
12
Coordinator
Roberto Segala
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Teaching is organised as follows:
Activity Credits Period Academic staff Timetable
Teoria 8 I semestre Roberto Segala
Laboratorio 4 I semestre Roberto Segala

Lesson timetable

I semestre
Activity Day Time Type Place Note
Teoria Tuesday 9:30 AM - 11:30 AM lesson Lecture Hall A  
Teoria Tuesday 4:30 PM - 6:30 PM lesson Lecture Hall B from Oct 28, 2010  to Jan 31, 2011
Teoria Wednesday 2:30 PM - 3:30 PM lesson Lecture Hall B from Oct 18, 2010  to Jan 31, 2011
Teoria Wednesday 2:30 PM - 3:30 PM lesson Lecture Hall A from Oct 6, 2010  to Oct 15, 2010
Laboratorio Wednesday 3:30 PM - 5:30 PM lesson Lecture Hall B from Oct 18, 2010  to Jan 31, 2011
Laboratorio Wednesday 3:30 PM - 5:30 PM laboratorio Lecture Hall A from Oct 6, 2010  to Oct 15, 2010

Learning outcomes

Provide the foundamental tools to design algorithmic solutions for concrete programs. The algorithms are evaluated and compared based required amount of resources.

Syllabus

Complexity: complexity of algorithms, asymptotic notation, resolution of recurrence equations, amortized analysis.
Sorting and selection: insertion sort, merge sort, heap sort, quick sort, randomized quick sort. Linear algorithms, counting sort, radix sort, bucket sort. Selection algorithms.
Data structures: heap, binary search trees, RB-trees, B-trees, binomial heaps, hash tables, priority queues, disjoint sets, extension of data structures, graphs.
Design and analisis of alsorithms: divide et impera, greedy, dynamic programming, local serch, backtracking, branch and bound.
Foundamental algorithms: minimum spanning tree (Prim and Kruskal), linear programing (simplex and basic elements of the elipsoid method) shortest path with single source (Dijkstra and Bellman-Ford) and multiple source (Floyd-Warshall and Johnson), maximum flow (Ford-Fulkerson, Karp), maximnal matching on bipartite graph. A* algorithm as evolution of branch and bound.

Assessment methods and criteria

The exam consists of a writtene test of three hours, divided into two parts, and possibly of an oral colloquium.

The forst part of the written test consists of several questions with multiple choices. It produces a valuation from 0 to 30. The exam is not passed if the evaluation is below 18. The exam ends if the evaluation is between 18 and 23. The second part of the written test, available only if the evaluation of the first part is at least 24, consists of one or more exercises of increasing complexity. The evaluation is between 24 and 30.

The optional oral examination is available only if the evaluation of the second part of the written test is at least 27.