Politecnico di Torino
Politecnico di Torino
Politecnico di Torino
Academic Year 2007/08
Computer Algorithms
1st degree and Bachelor-level of the Bologna process in Telecommunication Engineering - Torino
Teacher Status SSD Les Ex Lab Tut Years teaching
Durante Luca ORARIO RICEVIMENTO     3.5 1 0.5 0 4
SSD CFU Activities Area context
ING-INF/05 5 B - Caratterizzanti Ingegneria informatica
Objectives of the course
The present module completes the basic programming course: the passage from analytical to design skills is enhanced. The module presents 'classical' algorithmic solutions of problems: both their underlying theory and their implementation in the "C" language are taken into account. It examines meaningful examples and case studies solved through algorithmic strategies in the 'C' language.
modules of "Fundamentals of Computer Science" and "Programming Techniques and Languages".
' Algorithms analysis: asymptotic analysis and worst case complexity; Big-Oh, Theta and Omega notations.
' Data structures: data representation; pointers (or references to objects); static memory allocation, stack and dynamical memory allocation; linked data structures; runtime memory management; data structure choice strategy.
' Recursion: recursion concepts, recursive mathematical functions; simple recursive procedures; backtracking; divide and conquer strategies; asymptotic analysis of recursive algorithms: recurrences.
' Elementary algorithms: quadratic sort (selection, bubble and insertion sort), linear sort (counting sort) and nlogn sort (quicksort, heapsort, mergesort); graphs and trees traversal.
' Algorithmic paradigms: divide and conquer, greedy, dynamical programming.
' Classical algorithms: hash tables, binary search trees, graphs algorithms, minimal path, minimal covering trees, flow network.
Laboratories and/or exercises
Practice lessons follow theory lessons and take place in rooms and laboratory, and consist of the development of "C" programs.
' The C Programming Language (2nd Edition), by Brian W. Kernighan, Dennis M. Ritchie, Prentice Hall Software Series.
' Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), by Robert Sedgewick, Addison Wesley.

Programma definitivo per l'A.A.2006/07

© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)