Algorithms and Data Structures (2008/2009)

Course partially running

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

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
The goal of this course is to improve the ability about the object oriented programming.


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
Lesson 1: Interface, Javadoc and Exception: concept and practice.

Lesson 2: An example of implementation of ADTs List, Queue and Stack.

Lesson 3: Use of Comparable interface. Technique to compare implementations. QuickSort and MergeSort comparison.

Lesson 4: ADT HashTable implementation.

Lesson 5: A dynamic programming algorithm implementation: Longest Common Subsequence (LCS).

Lesson 6: Implementation of ADT Tree and Binary Search Tree. Use of Iterator interface. Traversal methods implementation.

Lesson 7: A greedy algorithm implementation: Kruskal's algorithm.

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
A written test about some advanced data structures and algorithm paradigms implemented in Java language.

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