Discrete Mathematics and Algebra (SF2714)
Credits: 7.5, Grades: A-F, Language: English, Literature: Biggs, Discrete Mathematics (2nd ed.) + handouts + supplementary electronic material available below
Coordinator: Petter Brändén, Lindstedtsvägen 25, room 3532, phone: 790 72 51, e-mail: pbranden[at]math.kth.se, homepage
Aim: To give an introduction to discrete mathematics and algebra for further studies in discrete mathematics, algebra and related subjects.
By the end of the course the student should be able to solve problems, prove theorems and have an understanding of the topics discussed. In particular the student should
• be able to perform computations in integer and modular arithmetics,
• be able to use the Euclidian algorithm to find gcd's of integers and polynomials,
• have an understanding for and make computations in groups, rings and fields,
• be able to solve basic problems in enumerative combinatorics and graph theory,
• be able to construct error-correcting codes and to determine how many errors a code corrects,
• be able to construct correct proofs.
Syllabus: Integer and modular arithmetics, sets, binomial theorem, inclusion-exclusion, linear recursions, equivalence realtions, graphs, groups, rings, fields, polynomials, error-correcting codes. Chapters in Biggs: 7.1-3, 8, 10, 11.1-5, 12.1-5, 13.1-13.3, 15, 17.4-17.6, 20, 21.1-4, 22, 23.1-4, 24.1-4
Prerequests: Linear algebra 5B1109 (SF1604)
Examination: Written exam (no calculators allowed) and homework
Homework I: PDF
Homework II: PDF
Supplementary material: Stanley's exercises on Catalan numbers with solutions, Wilf's book generatingfunctionology
Recommended Exercises:
Biggs, Chapter 8: 1.1-1.3, 2.1, 2.2, 4.1, 5.3, 6.1, 6.3, 7.1,7.3, 7.4, 7.9
Handout on integer/modular arithmetics: 6.1.1, 6.1.2a,c,d, 6.1.3, 6.1.6a, 2.3.33b,c, 2.3.35
Biggs, Chapter 20: 2.2, 2.4, 3.1-3.3, 4.2, 4.5, 5.4, 6.1, 7.3, 7.4, 8.4, 8.5
Biggs, Chapter 12: 6.1, (6.5)
Biggs, Chapter 22: 1.1, 1.2, 2.1, 2.3, 3.2, 3.3, 4.5, 5.1-5.4, 6.1-6.4, 9.2, 9.5, 9.6, 9.9, 9.17
Handout on rings, fields and polynomials: 43.19, 43.20, 45.1-45.6, 45.9, 45.10, 45.14-45.17, 45.19, 46.1, 46.6, 47.6-47.11, 49.1, 49.4-49.7
Handout on enumerative combinatorics: 1, 2, (6)
Exercises in generatingfunctionology: p 25: 3, 6, 9, 11, p 65: 4
Catalan exercises: n, o, r, ff, ii
Biggs, Chapter 15: 1.4, 2.1, 3.1, 3.2, 3.5, 4.4, 5.3, 5.4, 6.1, 6.2, 7.2, 7.4, 8.1, 8.5
Biggs, Chapter 24: 1.1, 1.4, 2.1, 2.2, 3.1, 3.2, 4.1, 4.2, 4.4