


Politecnico di Torino  
Academic Year 2009/10  
10EIPFN Computer Algorithms 

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





Objectives of the course
This course, mandatory for all the students, has a twofold objective: on one hand, to extend the use of programming as a way to solve problems; on the other hand, to study the basic concepts for formulating algorithmic solutions to concrete problems. In particular, the course will study solutions to problems formulated in terms of abstract mathematical structures (lists, queues, graphs) and methodologies for identifying the abstract problems that are best suitable to the analysis of a concrete problem, while keeping a tight relation with their implementation into a computer program.

Expected skills
The course has three main objectives: make the student capable of solving concrete problems using an algorithmic approach; assess the efficiency of the chosen algorithm in terms of execution time; implement such solutions as computer programs. These skills will be applied to the solution of practical problems, be they tractable (thus with a polynomialcost solution) or not (thus with heuristic, approximate solutions).

Prerequisites
The main prerequisites are the knowledge of the C programming language (at the level taught in the Computer Sciences course), as well as some basic notion of Calculus.

Syllabus
1.Advanced C Programming [20 hours]
a.Modular Programming b.Recursion i.The concept of recursion and its implementations; ii.Recursive mathematical functions. b.Abstract Data Types (ADT) and data structures: i.Abstraction and interface ii.Queue, stacks, dynamic arrays iii.Linear lists and trees 2.Basic concepts about algorithm [6 hours] a.Complexity of algorithms: i.Asymptotic notation, worstcase complexity; ii.Recurrence equations and their solution 3.Sorting and selection [10 hours] a.Insertion ion sort, merge sort, heap sort, quick sort, probabilistic quick sort. b.Study of the complexity of sorting algorithms; theoretical limits of sorting based on comparisons; c.Linear algorithms d.The selection problem 4.Abstract Data Types (ADT) [16 hours] a.Queue, stacks, lists, heaps; b.Trees: Binary search trees, RedBlack Trees c.Hash Tables 5.Algorithmic paradigms [10 hours] a.divide and conquer b.greedy algorithms c.dynamic programming d.searchbased paradigms: backtracking 6.Grafi [18 hours] a.Definition and representation of graphs; b.Breadthfirst and depthfirst visits; topological sorting, connected and strongly connected components c.Minimum spanning trees: Prim's and Kruskal's algorithms d.Singlesource shortest paths (Dijkstra's and BellmanFord's algorithms) e e.Allpairs shortest paths (FloydWarshall's algorithm) 7.Complexity theory [4 hours] a.Nondeterminism and nondeterministic algorithms b.The P and NP classes c.Approximations and heuristics 
Laboratories and/or exercises
The course includes about ten hours of lab, in which some of the algorithms presented in class will be implemented as C programs.

Bibliography
 Handouts of class material.
 T. Cormen, C. Leiserson, R. Rivest, C. Stein, 'Introduction to Algorithms', 2nd edition, McGrawHill.  H.M.Deitel e P.J.Deitel, 'C: How to Program', 6th edition, PrenticeHall 
Check availability at the library 
Revisions / Exam
The exam consists of a written test structured in two parts. The first part aims at assessing the students' knowledge of the theoretical aspects of the course (algorithms and data structures); the second part concerns the practical application of the theoretical topics, and consists in writing on paper of a C program that implements the solution of a practical problem that requires nontrivial algorithms or data structures.

