Weekly outline

  • General

    Discrete Structures by Prof. Amin Shokrollahi

    Teaching Staff

    Primary Teaching Staff

    Amin Shokrollahi
    • Will be teaching the classes
    • Office hours: Send e-mail for appointment
    • Email: amin dot shokrollahi at epfl dot ch
    Anna-Lena Horlemann
    • Responsible for exercises and classes
    • Office hours: Send email for appointment
    • Email: anna-lena dot horlemann at epfl dot ch

    Exercises - Doctoral Assistants

    Manos Karpathiotakis
    • Co-responsible for exercises
    • Office hours: Tuesdays, 10 am-12 pm, BC 230
    • Email: manos dot karpathiotakis at epfl dot ch
    Nooshin Mirzadeh
    • Co-responsible for exercises
    • Office hours: Wednesdays, 5pm-6pm, INJ 215
    • Email: nooshin dot mirzadeh at epfl dot ch
    Tam Nguyen Tanh
    • Co-responsible for exercises
    • Office hours: Fridays, 2pm - 4pm, BC 130
    • Email: tam dot nguyenthanh at epfl dot ch

    Student Assistants

    • Johannes Beck
    • Léa Bommottet
    • Henry Decléty
    • Anseleme Goetschmann
    • Léonore Guillain
    • Mehdi Karoui
    • Isaac Leimgruber
    • Raphael Laporte
    • Romain Leteurtre
    • Thévie Mortiniera
    • Karine Perrard
    • Lucas Ramirez
    • Sébastien Speierer
    • Pierre Thévenet
    • Thimoté Vaucher

    Practical informations

    Where, when

    We will have two classes a week, both in CO1

    • Tuesdays from 8:15 to 10:00
    • Fridays from 8:15 to 10:00

    Exercise sessions will be Fridays from 10:15 to 12:00 in the rooms given in the following table:


    NOTE: The table has changed (again - 25.09.2015) due to an increase in class enrollment!




    Sciper NumberRoom
    From (inclusive)To (inclusive) 
    196046244960CM012
    244967246640
    INM10
    246658250624INM200
    250680258259INJ218
    258263264333CO2


    The Book we Will Follow

    We will follow the book “Discrete Mathematics and its Applications” by Kenneth Rosen

    • 7th Edition
    • Global Edition
    • Book can be purchased at La Fontaine
    • You are supposed to read the book in parallel to the class

    How to Pass this Course

    • There is no contrôle continu;
    • ONLY grade in final exam counts;
    • If you perform well on the exercises, you should be fine;
    • We will have one exercise sheet per week
      • The solutions will be published right before the exercise session of the week after;
      • The exercise sheet will be on moodle right before the exercise session;
    • The final exam will be three hours;
    • After the exams are graded, you will have ONE chance to challenge the grade during a certain period
      • You will have only this one chance, so use it wisely;
      • No grade modification poossible outside the challenge period;
      • The challenge period will be communicated through moodle;
    • Calculator may be useful for exercises;
    • Calculator not needed at exams;
    • No actual programming: no laptop needed;
    • Book is sufficient for following the course;
    • Exam is Closed Book, that is:
      • Calculators, laptops, phones, iAnything, notepads, other electronic equipments, books, or anything other than your pen and white sheets of paper ARE NOT ALLOWED.
      • Catching you with any of these counts as a cheating attempt.

    What we Will be Learning

    • Precision
      Write and think clear and precise statements
    • Formal reasoning
      Inference, proof techniques
    • Intuitive set theory
      Sets and operations on them, comparing sets, surprising facts about infinite sets
    • Methods for analyzing growth of functions
    • Elementary and recursive algorithms
    • Elementary number theory
      Congruences and what can be done with them
    • Induction techniques
    • Counting
      Combinatorics, methods for counting
    • Discrete probability theory
    • Generating functions
    • Graph theory
    • 14 September - 20 September

      15.09.2015: Propositional Logic [Pages 1-12, 22-28]

      • What is a proposition
      • Compound propositions: negation, conjunction, disjunction, XOR
      • Truth tables
      • Conditional, biconditional
      • Converse, inverse, contrapositive
      • Logical equivalence
      • Tautology and contradiction
      • De Morgan's laws



      18.09.2015: Predicates and Quantifiers [Pages 34-48, 53-60]

      • What is a predicate
      • Examples of predicates
      • Universal and existential quantification
      • Equivalence of quantified predicates
      • Quantification and logical operators
      • Negation of quantifiers
      • Nested quantifiers and their ordering
      • First examples of inference



    • 21 September - 27 September

      22.09.2015: Proof techniques [Pages 62-74, 83-93]

      • Continued with inference
      • Proof techniques
      • Direct proofs
      • Proofs by contraposition
      • Proofs by contradiction
      • Non-constructive existence proofs


      25.09.2015: Elementary Set Theory [Pages 117-134]

      • Intuitive definition of a set
      • Set notation
      • Set operations
      • Set identities
      • Inclusion and exclusion principle
    • 28 September - 4 October

      29.09.2015: Inclusion-exclusion and functions [Pages 134-146, 140-153]

      • Inclusion-exclusion examples
      • Definition of a function
      • Injectivity, surjectivity, bijectivity
      • Properties of functions


      02.10.2015: Cardinality [Pages 168-179]

      • Cardinality of sets
      • Countability of N, Z
      • Countability of Q
      • Uncountability of R
      • Special functions
    • 5 October - 11 October

      06.10.2015: Mostly historic overview, a little bit of sequences

      • Definition of a sequence
      • Some examples


      09.10.2015: Arithmetic and geometric sequences, matrices

      • Closed formulas for some special sums
      • Sums of arithmetic and geometric sequences
      • Matrix addition and multiplication
    • 12 October - 18 October

      13.10.2015: Algorithms and Big-O

      • Examples of algorithms (finding maximum, searching in unordered and ordered sequences, sorting etc.)

      • Cost of these algorithms (constant, linear, logarithmic, quadratic)

      • The Big-O notation


      16.10.2015: Algorithms and Big-O

      • More on Big-O
      • When is a function f not O(g) for some other function g
      • More examples of Big-O
      • Omega, Theta, little-o
      • mod and div operations

    • 19 October - 25 October

      20.10.2015: Congruences [pages 237-245, 263-268]

      • Congruences modulo an integer
      • Greatest common divisor
      • Euclidean algorithm
      • Greatest common divisor as a linear combination (Theorem of Bezout)
      • Solving congruences


      23.10.2015: Prime numbers [pages 253-262]

      • Little theorem of Fermat
      • How to prove that a number is not prime using Fermat's little theorem
      • Computer presentation of the algorithms
      • Theorems on prime numbers
    • 26 October - 1 November

      27.10.2015: Induction [pages 307 ff.]

      • Well orderedness principle
      • Mathematical induction
      • Proof of summation formula for geometric sum
      • Proof of n < 2^n
      • Proof that the harmonic sum up to 2^n is at least 1 + n/2
      • Using integration to conjecture that the sum of k^2 for k from 1 to n is n^3/3 + n^2/2 + n/6
      • Proof using induction
      • Strong induction: statement and proof using the well-orderedness principle
      • Proof that every integer is a product of (not necessarily) distinct primes


      30.10.2015: Induction and start of recursion [pages 307 ff.]

      • Strong induction and the game on Exercise 10, page 337
      • Reverse induction
      • AGM inequality
      • Beginnings of recursive algorithms
      • Factorial
      • Fibonacci numbers
    • 2 November - 8 November

      03.11.2015: Recursive algorithms [pp. 353-362, 364]

      • Basic structure
      • Recursive algorithm for exponentiation modulo m
      • Recursive sorting
      • Mergesort + analysis for lengths that are powers of 2
      • Quicksort + some analysis

      06.11.2015: Counting [pp. 375-376, 379-380, 388-390, 390-394]

      • Basic counting
      • Product rule and sum rule
      • Examples: number of function, number of injective functions, number of bit strings, size of power set
      • Pigeonhole principle
      • More general pigeonhole principle
    • 9 November - 15 November

      10.11.2015: Combinations and Permutations [pp. 395-400]

      • Permutation with/without replacement
      • Combinations without replacement
      • Examples


      13.11.2015: Combinations and Permutations continued [pp. 404-408, 410-415]

      • Combinations with replacement
      • Frequency of poker hands
      • Formulas involving binomial coefficients
    • 16 November - 22 November

      17.11.2015: Discrete probability 

      • probability distributions
      • probability of events, union of events, complementary events
      • conditional probability
      • independence of two events
      • pairwise/mutual independence for several events


        20.11.2015: Discrete probability 

        • Bayes' theorem
        • random variables
        • expected values
        • Bernoulli trial, binomial distribution
        • independence of random variables

      • 23 November - 29 November

        24.11.2015: Discrete probability 

        • Markov inequality
        • Variance of random variables
        • Chebyshev inequality
        • Tightness of Chebyshev inequality
        • Chebyshev inequality for Bernoulli trials
        • The Monty Hall problem and class demonstration


        27.11.2015: Generating functions [Section. 8.2 and part of 8.4] 

        • Generating function of a sequence
        • How to obtain a closed form for the elements of the sequence
        • How to find out the growth of the terms
        • Various examples
      • 30 November - 6 December

        01.12.2015: Graphs [pp. 617-646] 

        • Definition of an undirected graph
        • Examples
        • Complete and bipartite graphs
        • Subgraphs
        • Graph isomorphism
        • Degree of nodes
        • Adjacency matrix
        • Directed graphs: node degrees, adjacency matrix


        04.12.2015: Paths, planarity, Euler's Formula [Sect. 10.4, 10.5, 10.7] 

        • Connectedness
        • Connectedness and adjacency matrices
        • Euler paths, necessary and sufficient conditions
        • Planarity
        • Euler's formula
      • 7 December - 13 December

        08.12.2015: Graphs [pp. 682-689] 

        • Trees
        • Uniqueness of paths
        • Number of edges
        • Minimality of number of edges
        • Weighted graphs
        • Dijkstra's algorithm with example
        • Proof of correctness


        11.12.2015: The PageRank Algorithm

        • Popularity in directed graphs
        • Random walks
        • Perron-Frobenius Theorem
        • PageRank
      • 14 December - 20 December

        15.12.2015: Linear Codes

        • Binary linear error-correcting codes
        • Generator matrix, check matrix
        • Correcting errors
        • Hamming codes
        • Examples


        18.12.2015: Fountain  Codes

        • Data distribution on the Internet
        • TCP and UDP protocols
        • Fountain codes
        • Raptor codes
        • Demo


        Parts of the book the exam will cover (Global Edition = 7th Edition of the book):

        • Sections: 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.8, 1.9
        • Sections: 2.1, 2.2, 2.3, 2.4, 2.5, 2.6
        • Sections: 3.1, 3.2, 3.3 [until page 224]
        • Sections: 4.1, 4.3, 4.4
        • Sections: 5.1, 5.2, 5.3, 5.4
        • Sections: 6.1, 6.2, 6.3, 6.4
        • Sections: 7.1, 7.2, 7.3, 7.4
        • Sections: 8.2, Table I on p. 526 can be useful, 8.5
        • Sections: 10.1 [only definition of graphs], 10.2 [until page 633], 10.3 [Adjacency matrices], 10.4 [until page 661, 10.5 [Euler paths only], 10.6 [Dijkstra's algorithm], 10.7 [Until page 694]
      • 18 January - 24 January

        The final exam will be on January 21, from 8:15 am to 11:15 am, in the rooms CE1, CE4, and Salle Polyvalente. 

        Every student has an individualised seat number in a corresponding room. The assignment of sciper numbers to the pair (room, seat number) is given in the files below. 

        • Sciper numbers 196046 through 250394 inclusive will be in Room CE1.
        • Sciper numbers 250473 through 260036 inclusive will be in Room CE4.
        • Sciper numbers 260233 through 265339 inclusive will be in Salle Polyvalente.