Ämnesdisposition

  • Allmänt

    Lärare:
    Backelin, Jörgen

    Kursspråk/Language:

    Föreläsningarna kommer att hållas på svenska, såvida inte minst en student önskar att de hålles på engelska. Skrivningens språk kommer också att anpassas efter studenternas önskemål.

    The lectures will be taught in English, if at least one student wishes this to be the case; else they will be held in Swedish. Likewise, the language of the written exam will be (reasonably) accommodated to the needs of the students.


    Schedule

    Course contents 

    The goal of this class is to learn the basic notions and principles of combinatorics such as permutations, graph theory, trees and search algorithms, directed graphs, recursive methods, generating functions, partitions.

    Textbook

    Grimaldi, Discrete and combinatorial mathematics, 5th edition, Addison-Wesley

    Examination

    There will be a final written exam. We may at the course start agree on supplementing this with bonus-enablng  studentactivities.

    Tentative plan of the course:

    The listed exercises are recommendations. In general, they should be made to the lecture after the one where they are listed. You may well do more excercises.

    It is also important that you also checks that you understand the underlying terminology, whether or not it appears in exercises. Inter alia, employing and understanding basic set notation is absolutely indispensable in this course.

    Day 1: Fundamentals; counting principles

    Text: 1.1-1.4
    Exercises:
    1.2: 10,16,20,22,32,34,36
    1.3: 10,12,16,18,20,26,28,30
    1.4: 2,4,10

    Day 2: Sets, functions, pidgeon hole principle
    Text: 5.1-5.3, 5.5
    Exercises:
    5.3; 8,10,17
    5.5: 4,8,10,12,20

    Day 3: Inclusion-exclusion formula, derangements
    Text: 8.1-8.3
    Exercises:
    8.1: 4,16,20;
    8.2: 2,4;
    8.3: 4,6,10

    Day 4: Rook polynomials, generating formal power series
    Text: 8.4-8.6, 9.1-9.2
    Exercises:
    8.5: 4,6,12
    9.1: 2 (here r pennies instead of 35 pennies make more sense)
    9.2: 2,4,6,8,10,16,30

    Day 5: Exponential generating formal power series
    Text: 9.3-9.5
    Exercises:
    9.3: 2,4,10
    9.4: 2,4,6
    9.5: 2,4

    Day 6: Linear recursions
    Text: 10.1-10.2
    Exercises:
    10.1: 2
    10.2: 4,12,14,22,24

    Day 7: Solving recursions with generating formal power series
    Text: 10.2-10.4
    Exercises:
    10.2: 26,28
    10.3: 2,6,8,12
    10.4:1

    Day 8: Graphs, subgraphs, isomorphic graphs, degree, Euler paths
    Text: 11.1-11.3
    Exercises:
    11.1: (2),4,(8),(10),14
    11.2: (2),6,8,10,12
    11.3: 2,4,8,10,20,22,(24),30

    Day 9: Hamilton paths, planarity
    Text: 11.4-11.5
    Exercises:
    11.4: 2,6,(8),(10),12,14,18,22
    11.5: (2),6,8,10,12,18
    In 11.5 10b assume again that |V_1| <> |V_2| as in (a).

    Day 10: Coloring, chromatic number, chromatic polynomials
    Text: 11.6
    Exercises:
    11.6: (2),(4),6,8,10,14,16

    Day 11: Trees and applications
    Text: 12.1-12.2
    Exercises:
    12.1: 2,4,(6),8,10,(12),16,(18)
    12.2: 2,8,10,16

    Day 12: Combinatorial optimization problems: shortest paths, minimal spanning tree
    Text: 13.1-13.2
    Exercises:
    13.1: 2
    13.2: 2,4

    Day 13: Flows and matchings
    Text: 13.3-13.4
    Exercises:
    13.3: 4,6 (find in 4 also the corresponding minimal cut); always try to start with a flow with large flow value
    13.4: 2,(4),6,8

    Day 14: Reserve, review

    Day 15: Review