Course Details for A.Y. 2013/2014
Name:
Laboratorio di Algoritmi e Strutture Dati / Lab. of Algorithms and Data Structures
Basic information
Credits:
: Laurea in Informatica 6 CFU (b)
Degree(s):
Laurea 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: 13 maggio 2014, 13:12