# Course Details for A.Y. 2012/2013

#### Name:

**Laboratorio di Algoritmi e Strutture Dati / Lab. of Algorithms and Data Structures**

### Basic information

##### Degree(s):

Laurea Base in Informatica 2° anno curriculum Generale Obbligatorio

##### Language:

Italian

### Course Objectives

KNOWLEDGE: elementary and (some) advanced data structures and their definition in the C programming language; major
techniques for designing algorithms; use of the design techniques and of the data structures to solve problems and to implement efficient solutions in C.
ABILITIES: a student completing this course should be able to use some techniques for designing algorithms and data structures to solve problems. Students are also expected to implement in C and analyze solutions (with respect to computational complexity and correctness).
EXPECTED BEHAVIOUR: interest in using the C programming language to solve problems and testing their solutions on computer.

### Course Content

- Elementary data structures: linked lists, stacks and queues. Implementation of basic operations. Data structures for disjoint sets.
- Binary trees: representations by arrays (positional trees) and linked data structures; implementation of basic operations; breadth-first search and depth-first search.
- Sorting algorithms: implementation of bubble-sort, insertion-sort, selection-sort, merge-sort, quick-sort
- Priority queues: binary heaps and use of a heap to implement a priority queue; implementation of basic operations; implementation of heap-sort
- Binary search trees (BST): representation and implementation of basic operations; rotations. Balanced BST: 2-3-4 search trees; red-black trees
- Graphs: representations, implementation of breadth-first search and depth-first search; implementation of elementary graph algorithms: single-source shortest paths and minimum spanning trees.

### Prerequisites and Learning Activities

Students should have some programming experience in C language. In particular, they should understand recursive functions and simple data structures such as arrays and linked lists

### Assessment Methods and Criteria

Written and oral exam.

### Textbooks

- Robert Sedgewick, Algoritmi in C , Addison-Wesley. 2002. terza edizione
* *
- P. Crescenzi, G. Gambosi, R. Grossi, G. Rossi, Strutture dei dati e algoritmi: Progettazione, analisi e programmazione , Pearson. 2012. seconda edizione
* *

### Course page updates

This course page is available (with possible updates) also for the following academic years:

** To read the *** current * information on this course, if it is still available, go to the university course catalogue .
*Course information last updated on: 24 aprile 2013, 16:09*