ALGORITHMS AND DATA STRUCTURES I
cod. 23640

Academic year 2007/08
2° year of course - Second semester
Professor
Academic discipline
Informatica (INF/01)
Field
Formazione interdisciplinare e applicativa
Type of training activity
Related/supplementary
48 hours
of face-to-face activities
6 credits
hub:
course unit
in

Learning objectives

The goal of the course is to familiarize students with algorithms, data structures and with the techniques needed for analyzing  their efficiency. <br /><br />

Prerequisites

Each student is expected  to know the basic concepts of discrete mathematics,  and calculus. <br /><br />

Course unit content

<br /> <br /><br /> Models of computation, analysis of algorithms.<br />Basic data structures: linked lists,  stacks, queues, trees.<br />Basic sorting  algorithms, lower bounds for sorting.<br />Quicksort, heapsort. Sorting  in linear time.<br />Median and order   statistics.<br />Divide and conquer technique.<br />Introduction to dynamic programming and greedy technique.<br />Huffman  trees. Binary trees, binary search trees, B-trees, red-black trees.<br />Hash tables.<br />Graphs, BFS,DFS, directed acyclic graphs, topological sort and strong components.<br />Union-find, MST, Kruskal's algorithm, Prim's algorithm.<br />Dijkstra's algorithm, Bellman-Ford algorithm.<br />

Full programme

- - -

Bibliography

<br /><br />T. Cormen, C. Leiserson, R. Rivest, C. Stein,  Introduction  to Algorithms,  McGraw-Hill;<br />C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati, McGraw-Hill. <br />

Teaching methods

- - -

Assessment methods and criteria

- - -

Other information

- - -