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 Mechatronic Engineering - Verres/Ivrea
Teacher Status SSD Les Ex Lab Tut Years teaching
SSD CFU Activities Area context
F - Altre (art. 10, comma 1, lettera f)
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.
' 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.2011/12

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