


Politecnico di Torino  
Academic Year 2010/11  
02JSHOT, 02JSHNG Discrete Mathematics 

Master of sciencelevel of the Bologna process in Telecommunications Engineering  Torino Master of sciencelevel of the Bologna process in Mathematical Engineering  Torino 





Esclusioni: 02KRR 
Subject fundamentals
The course is taught in English.
The main aim of the course is to provide a basic introduction to some standard techniques of combinatorial mathematics and discrete structures such as graphs and trees. Emphasis will be given to several problems (such as questions concerning tiling and counting, decision trees, estimates on the complexity for recursive procedures, etc.) which admit a natural formulation within the framework of discrete mathematics. 
Expected learning outcomes
The knowledge obtained from this course will include several standard techniques of combinatorial mathematics, with emphasis on possible applications. In particular, by the end of the course, it is expected that students will be able to set out, formulate precisely and solve typical problems in combinatorial mathematics, especially those arising in applications.

Prerequisites / Assumed knowledge
Basic notions on sets and functions, and some basic calculus are required.

Contents
The wellordering axiom, strong and weak form of the induction principle (6 hours).
Basic counting problems. Decision trees and recursive processes (6 hours). Functions and counting, the pigeonhole principle, the multiplicative principle, the additive principle (8 hours). Ordered and unordered selections with and without repetition. Permutations, binomial and multinomial coefficients, the binomial formula. The sieve principle (8 hours). Generating functions and linear recurrences (8 hours). Ordered and unordered graphs, walks, paths, cycles. Eulerian walks and Hamiltonian cycles. Trees. Combinatorics of graphs. Planar graphs, Euler formula and its corollaries (12 hours). Complexity lower bounds via decision trees and optimal strategies. Applications and examples, in particular to tiling problems, searching and sorting algorithms (12 hours). 
Delivery modes
Exercises during tutorials will cover the subjects discussed during the lectures, and will be carried out by the teacher.

Texts, readings, handouts and other learning resources
Lecture Notes on "Discrete Mathematics" by L. Lovász and K. Vesztergombi.
Norman L. Biggs, Discrete Mathematics, Clarendon Press, Oxford, 1985. 
Assessment and grading criteria
Written examination.

