Course Details for A.Y. 2013/2014

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    

Internet Resources

Course page updates

• A.Y. 2010/2011
• A.Y. 2011/2012
• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019
• A.Y. 2019/2020