


Politecnico di Torino  
Academic Year 2007/08  
01EIPBN Computer Algorithms 

1st degree and Bachelorlevel of the Bologna process in Telecommunication Engineering  Torino 





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.

Prerequisites
modules of "Fundamentals of Computer Science" and "Programming Techniques and Languages".

Syllabus
' Algorithms analysis: asymptotic analysis and worst case complexity; BigOh, 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.

Bibliography
' The C Programming Language (2nd Edition), by Brian W. Kernighan, Dennis M. Ritchie, Prentice Hall Software Series.
' Algorithms in C, Parts 15 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), by Robert Sedgewick, Addison Wesley. 
