Fundamentals of Discrete Mathematics


Course description
 

The main goal of the course is  to present some basic facts and techniques about "counting". We will deal with finite sets and their subsets, permutations, factorials, binomial coefficients, Pascal's triangle, the Binomial Theorem, prime numbers and divisors, linear recurrences (with particular attention to Fibonacci numbers), generating functions. We will also study some discrete structures such as graphs and trees, and discuss some classical problems and algorithms in this setting. Finally, we will discuss some applications of discrete mathematics to the analysis of certain basic algorithms (e.g. classical sorting algorithms) and their computational complexity.


 

Lectures Schedule/Topics

Exam information

Material

A nice introduction to the subject is represented by the classical Lecture Notes on "Discrete Mathematics" by L. Lovász and K. Vesztergombi, which are freely available:
      
       PostScript file:   http://www.cs.elte.hu/~lovasz/notes.html

       PDF file:   http://openpdf.com/ebook/discrete-mathematics-lecture-notes-dmbook-lovasz-pdf.html

Other free sources of material (with a lot of exsamples and exercises) are the following:

                   PDF file available at   http://www.math.northwestern.edu/~mlerma/papers/

   
                   PDF version (file name "Discrete mathematics - MTH 202") available at   http://home.iitk.ac.in/~arlal/publication_pipeline.htm


                   PDF file (free, but please read "Terms and Conditions") available at   http://www.math.upenn.edu/~wilf/AlgComp3.html