DISCRETE MATHEMATICS
LEARNING MODULE DESCRIPTION (SYLLABUS)
I. General information
1. Module title: DISCRETE MATHEMATICS
2. Module code: 06-DMAD LI0
3. Module type – compulsory or optional
4. Programme title
5. Cycle of studies: 1st cycle of studies
6. Year of studies (where relevant) 1st
7. Terms in which taught :spring term
8. Type of classes and the number of contact hours ( lectures: 30 hours; practical classes: 30 hours)
9. Number of ECTS credits: 6
10. Name, surname, academic degree/title of the module lecturer:
dr hab. Edyta Szymańska, assistant professor
edka@amu.edu.pl
11. Language of classes: English
II. Detailed information
1. Module aim (aims): Learn basic notions, problems and techniques of discrete mathematics and graph theory.
2. Pre-requisites in terms of knowledge, skills and social competences: foundations of logic and set theory
3. Module learning outcomes in terms of knowledge, skills and social competences and their reference to programme learning outcomes: get to know basic notions and theorems of discrete mathematics and prepare to study other subjects in computer science.
Learning outcomes symbol* | Upon completion of the course, the student will: | Reference to programme learning outcomes^{#} |
E_01 | know basic rules and principles of counting | KINF1_W03 |
E_02 | prove simple combinatorial identities | KINF1_U01, KINF1_U04 KINF1_W03 |
E_03 | identify selected recurrence relations and solve them | KINF1_U01, KINF1_W03 |
E_04 | comprehend and know how to use basic concepts of graph theory | KINF1_K01, KINF1_U01, KINF1_U04 |
E_05 | comprehend and know how to use classic graph algorithms | KINF1_U04 |
E_06 | know classic examples of applications of graph theory | KINF1_K01, KINF1_W03 |
* module code, e.g. KHT_01 (KHT – module code in USOS; stands for Polish “Kataliza Heterogeniczna” /Heterogeneous Catalysis/ )
^{#} programme learning outcomes (e.g. K_W01, K_U01, … ); first K stands for programme title symbol in Polish, W for “wiedza” (knowledge) in Polish, U – for “umiejętności” (skills) in Polish, K – for “kompetencje społeczne” (social competences) in Polish
01, 02… - learning outcome number
4. Learning content
Module title: Discrete Mathematics II | ||
Learning content symbol* | Learning content description | Reference to module learning outcomes^{ #} |
T_01 | Methods of proving theorems: direct proofs, indirect proofs, proofs by contradiction, mathematical induction. | E_02 |
T_02 | Basic counting rules and principles: bijection rule, sum and product rules, principle of inclusion-exclusion, pigeonhole principle. | E_01 |
T_03 | Selection schemes and combinatorial identities: permutations and combinations with and without replacements, combinatorial identities. | E_01, E_02 |
T_04 | Recurrence relations. Simple recurrence relations, linear recurrence relations, complex recurrence relations. | E_03 |
T_05 | Basic terminology of graph theory. | E_04 |
T_06 | Computer representations of graphs. Graph search trees. | E_04, E_05 |
T_07 | Classic graph problems and algorithms | E_04, E_05, E_06 |
* e.g. TK_01, TK_02, … (TK stands for “treści kształcenia” /learning content/ in Polish)
^{#} e.g. KHT_01 – module code as in Table in II.3
5. Reading list
· V. Bryant, "Aspects of Combinatorics", Cambridge University Press, 1993
· Z. Palka, A. Ruciński, "Wykłady z Kombinatoryki" , WNT, Warszawa, 2004 (in Polish).
· K. A. Ross, Ch. R. B. Wright, "Discrete Mathematics", 5th ed., Prentice Hall, 2002
· J. A. Bondy, U. S. R. Murty, "Graph Theory with Applications", American Elsevier Publishing Co., Inc., 1976
· R.L.Graham, D.E. Knuth, O. Patashnik, "Concrete Mathematics", Reading, Massachusetts: Addison-Wesley, 1994
· Th. H. Cormen, Ch. E. Leiserson, R.L. Rivest, C. Stein, "Introduction to Algorithms", The MIT Press; 2 edition, 2001
· W. Lipski, W. Marek, "Analiza Kombinatoryczna", PWN, Warszawa 1986 (in Polish).
· R. J. Wilson, "Introduction to Graph Theory", Addison Wesley Longman 1996.
6. Information on the use of blended-learning (if relevant)
7. Information on where to find course materials
III. Additional information
1. Reference of learning outcomes and learning content to teaching and learning methods and assessment methods
Module title: Discrete Mathematics II | |||
Symbol of module learning outcome* | Symbol of module learning content^{#} | Methods of teaching and learning | Assessment methods of LO achievement^{&} |
E_01 | T_02,T_03 | lectures, exercises | homework, tests, problems for self study |
E_02 | T_01,T_03 | lectures, exercises | homework, tests, problems for self study |
E_03 | T_04, T_05 | lectures, exercises | homework, tests, problems for self study |
E_04 | T_06, T_07,T_08 | lectures, exercises | homework, tests, problems for self study |
E_05 | T_07, T_08 | lectures, exercises | homework, tests, problems for self study |
E_06 | T_08 | lectures, exercises | homework, tests, problems for self study |
E_07 | T_05 | lectures, exercises | homework, tests, problems for self study |
* e.g. KHT_01 – module code as in Table in II.3 and II.4
^{#} e.g. TK_01 – learning content symbol as in II.4
^{&} Please include both formative (F) and summative (S) assessment
It is advisable to include assessment tasks (questions).
2. Student workload (ECTS credits)
Module title: Discrete Mathematics I | |
Activity types | Mean number of hours* spent on each activity type |
Contact hours with the teacher as specified in the programme | 60 |
Independent study 1: homework | 60 |
Independent study 2: study for the midterm test | 15 |
Independent study 3: study for the final exam | 15 |
Total hours | 150 |
Total ECTS credits for the module | 6 |
* Class hours – 1 hour means 45 minutes
^{#}Independent study – examples of activity types: (1) preparation for classes, (2) data analysis, (3) library-based work, (4)writing a class report, (5) exam preparation, etc.
3. Assessment criteria:
Grade 5: above 90 %
Grade 4: above 70%
Grade 3: above 50%
4. Titles of classes
Syllabus: | |
Week 1 | Proof techniques and basic counting laws (incl. mathematical induction and the Pigeon-hole Principle). |
Week 2 | Selection schemes: permutations and combinations. |
Week 3 | Principle of inclusion-exclusion. |
Week 4 | Combinatorial identities. |
Week 5 | Recurrence relations. |
Week 6 | Complex recurrence relations. |
Week 7 | Solving recurrence relations. |
Week 8 | Basic notions of Graph Theory. |
Week 9 | Basic notions of Graph Theory. |
Week 10 | Connectedness. |
Week 11 | Trees and spanning trees. |
Week 12 | Counting spanning trees. |
Week 13 | Shortest paths. |
Week 14 | Euler tours and Hamilton cycles. |
Week 15 | Planar graphs and map colorings. |