Politecnico di Torino
Politecnico di Torino
   
Login  
it
Politecnico di Torino
Academic Year 2009/10
10EIPFN
Computer Algorithms
1st degree and Bachelor-level of the Bologna process in Mathematics In Engineering - Torino
Teacher Status SSD Les Ex Lab Tut Years teaching
Poncino Massimo ORARIO RICEVIMENTO PO ING-INF/05 54 12 18 0 6
SSD CFU Activities Area context
ING-INF/05 7.5 A - Di base Formazione informatica
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 polynomial-cost 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, worst-case 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, Red-Black Trees
c.Hash Tables

5.Algorithmic paradigms [10 hours]
a.divide and conquer
b.greedy algorithms
c.dynamic programming
d.search-based paradigms: backtracking

6.Grafi [18 hours]
a.Definition and representation of graphs;
b.Breadth-first and depth-first visits; topological sorting, connected and strongly connected components
c.Minimum spanning trees: Prim's and Kruskal's algorithms
d.Single-source shortest paths (Dijkstra's and Bellman-Ford's algorithms) e
e.All-pairs shortest paths (Floyd-Warshall's algorithm)

7.Complexity theory [4 hours]
a.Non-determinism and non-deterministic 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, McGraw-Hill.

- H.M.Deitel e P.J.Deitel, 'C: How to Program', 6th edition, Prentice-Hall
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 non-trivial algorithms or data structures.

Programma provvisorio per l'A.A.2009/10
Back



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