Please note that the lectures do not follow the lecture notes (or books) exactly. In the lectures, the emphasis is on the main ideas and the relationships between them, usually with some small examples. The lecture notes and books deal with the material more thoroughly, including additional examples and more details.
All material produced by the lecturer (additional notes, exercise sheets, solutions, etc.) are also made available via this webpage. If you miss a lecture, you should look here for any handouts that you may have missed. Solutions appear only after all the class(es) covering that exercise sheet have taken place.
Homework is set every week during the lectures on Wednesday. The handout containing the exercises is made available via this page as well. Students are expected to hand in solutions to the exercises by 4:55pm on the following Monday to the homework box 13 (on the Ground Floor of Columbia House). No late work can be accepted. The homework exercises are discussed in the susequent class on Tuesday. So the n-th set of exercises are given out on Wednesday of Week n with deadline at 4:55pm on Monday of Week (n+1), and covered in the class in Week (n+1).
Label all work with your name, the course number (MA210), the number of the class group you are in, and the name of your class teacher.
Corrected and marked work and full solutions will be handed back in the next class.
The homework does not count in any way towards your final mark for this course. The exercises are meant for you to test your understanding of the material, and to give your class teacher some indication of how you are coping with the course.
Some questions are intended to be challenging! Do not worry if there are some exercises that you are unable to complete.
Marks for homework do not necessarily predict performance in the final examination.
| Week | Topics | Exercises, solutions, handouts |
|---|---|---|
| 1 |
Basic principles of counting: addition rule, multiplication rule, Pigeonhole Principle. Ordered selections with or without repetition. Unordered selections without repetition. Binomial numbers. |
Exercises 1 Solutions Notes for lectures 1 and 2 |
| 2 | Unordered selections with repetitions. Binomial Theorem. Inclusion-Exclusion Principle. |
Exercises 2 Solutions Notes for lectures 3 and 4 |
| 3 | Multinomial numbers. Multinomial Theorem. Proof of Inclusion-Exclusion Principle. Introduction to recurrence relations. |
Exercises 3 Solutions Notes for lectures 5 and 6 |
| 4 | Introduction to generating functions. |
Exercises 4 Solutions (Updated; thanks to Talal for spotting errors.) |
| 5 | More on generating functions. |
Exercises 5 Solutions |
| 6 |
Binomial Theorem for negative exponents; Introduction to graphs - definition, basic graph parameters, Handshaking lemma, graph isomorphism; Walks, trails and paths, Eulerian graphs, Euler Theorem. |
Exercises 6 Solutions Notes for lecture 12 Suggested reading - Biggs: sections 15.1-3 |
| 7 | Connectivity, components, bipartite graphs and their characterization. |
Exercises 7 Solutions Notes for lectures 13 and 14 Suggested reading - Biggs: sections 15.4 (see also 15.7) |
| 8 |
Trees, forests and their characterization; Minimal spanning trees, Kruskal's Algorithm. |
Exercises 8 Solutions Notes for lectures 15 and 16 Suggested reading - Biggs: sections 15.4-5, 16.3 (be aware that we only covered Kruskal's Algorithm, not the others!) |
| 9 |
Graph colourings, chromatic number, greedy algorithm; Introduction to coding theory: binary codes, Hamming distance, error-detecting codes, error-correcting codes. |
Notes for lectures 17 and 18 Exercises 9 Solutions Suggested reading - Biggs: sections 15.6-7, 24.1-2 |
| 10 | Parity check code, d-repetition code; Linear codes, dimension of linear codes, minimum distance in linear codes; Construction of linear codes, parity-check matrix; Correcting errors in linear codes; Hamming codess. |
Notes for lectures 19 and 20 Exercises 10 Solutions Suggested reading - Biggs: sections 24.3-4 |
Last modified: 9th June 2009, 10:30 GMT by JS
Send comments to
webmaster