MATH2069 Discrete Mathematics and Graph Theory
General Information
This page contains information on the Intermediate Unit of Study MATH2069: Discrete Mathematics and Graph Theory.
This unit is offered in Semester 1.
The lecturer for this unit of study is Anthony Henderson.
For further information on Intermediate Mathematics and Statistics, refer to the Intermediate Handbook.
You may also view the Faculty Handbook entry for MATH2069 from the central units of study database.
- Credit point value: 6CP.
- Classes per week: Three lectures, one tutorial and one practice class.
MATH2069/2969 Information in 2009
Printed copies of this page were distributed in the first lecture. Note that this web-page is being updated throughout the semester, so the printed copy has become out of date. It is your responsibility to check this web-page regularly.Lecturer
Name: Dr Anthony Henderson
Room: Carslaw 805
Phone: 9351 3881
Consultation hour: Wednesday 1-2pm
Email: A.Henderson@maths.usyd.edu.au
Classes
Lectures, practice classes, and quizzes (joint for MATH2069 and MATH2969) will be held at the following times:
- Monday 2-3 pm, Carslaw 175
- Tuesday 2-3 pm, Carslaw 175
- Wednesday 2-3 pm, Carslaw 175
- Thursday 1-2 pm, Carslaw 175 (except that the quizzes in Weeks 5 and 11 will be held in Teachers College Assembly Hall 300)
In the practice classes you will work through a sheet of questions relating to the material in the preceding lectures; the solutions will be briefly discussed in the class. These questions will be similar to those in the quizzes. The question sheets are printed at the back of the books of lecture notes (see below), and also available on the web resources page, where the solutions will be posted after each week's class.
Tutorials (one per week) started in Week 2 for MATH2069 students, and Week 1 for MATH2969 students. There was a change to the MATH2969 tutorial time: starting from Week 3, it has been on Monday at 1pm in Carslaw 452. (MATH2969 students who cannot attend then may go to one of the MATH2069 tutorials.) The tutorial sheets are printed at the back of the books of lecture notes. (They will not be distributed in tutorials.) They are also available on the web resources page, where the solutions will be posted on the Monday of each week. The tutorials in Week 13 will be opportunities for you to try past exam questions; specifically, the 2008 exam papers will be useful practice.
Assessment
Your raw mark will be calculated as follows.- 60%: Exam
- 30%: Class quizzes (two, worth 15% each)
- 10%: Assignment
The exam (50% different for MATH2069 and MATH2969, 50% the same) will be held on Tuesday June 23, 1.50pm-4pm. It is a single 2-hour examination covering both halves of the unit (unlike in previous years, when there were separate discrete maths and graph theory exams). Here is the exam information sheet.
Past papers with solutions (and in some cases comments) are available on the web resources page. Note that the change to a single exam means that these past papers are not an accurate guide to length; moreover, the topics of planar graphs and directed graphs have been cut from the graph theory half in 2009, so some questions in past papers are no longer relevant.
The two quizzes (the same for MATH2069 and MATH2969) will be held in weeks 5 and 11, during the Thursday 1-2pm class times (not in the tutorials). The quizzes consist of short-answer questions where only the answers will be marked, similar to the practice class questions. More information on these quizzes will be posted here closer to the dates.
- Quiz 1, April 2, 1.05-1.50pm, Teachers College Assembly Hall 300: information
- Quiz 2, May 21, 1.05-1.35pm, Teachers College Assembly Hall 300: information
The assignment (different for MATH2069 and MATH2969) was posted on the web resources page, and was due on Thursday May 7. A late penalty of 10% per day applies (up to a week after the deadline).
Texts and References
The examinable content of the unit is all contained in the books of lecture notes: Topics in Discrete Mathematics by Anthony Henderson (revised in 2009) and Introduction to Graph Theory by Anthony Henderson (new in 2009). These may be purchased for $18 and $15 respectively from Kopystop, 55 Mountain Street, Broadway. Kopystop's phone number is 9211 2733.
Some other reference books, which you may want to consult for additional examples and exercises, are listed on the Acknowledgements page of the two books of lecture notes.
Course Outline
In the first half, we will study several related areas of discrete mathematics, which have applications throughout pure and applied mathematics, as well as in computer science and other sciences. In the second half, we will restrict our attention to one particular area of discrete mathematics, namely graph theory. We will investigate some of the fundamental results on Eulerian and Hamiltonian graphs, trees, and vertex colourings, among other topics. The sections expected to be covered in each week's lectures (approximately) are as follows.Week 1: Introduction to discrete mathematics, counting principles, ordered selection (0,1.1,1.2)
Week 2: Binomial coefficients, inclusion/exclusion, Stirling numbers (1.3,1.4,1.5)
Week 3: Recursive sequences, induction, homogeneous linear recurrences (2.1,2.2,2.3)
Week 4: Non-homogeneous recurrences, formal power series (2.4,3.1,3.2)
Week 5: Generating functions and recursion, sorting algorithms (3.3,4.1)
Week 6: Asymptotic comparison, growth rates (4.2,4.3)
Week 7: Introduction to graph theory, basic definitions (0,1.1,1.2)
Week 8: Degrees, Eulerian and Hamiltonian graphs (1.3,2.1,2.2)
Week 9: Minimal walks, trees (2.3,3.1)
Week 10: Spanning trees, Matrix-Tree Theorem (3.2,3.3)
Week 11: Vertex colourings, chromatic polynomial (4.1,4.2)
Week 12: Edge colourings (4.3) and non-examinable topics: matching theory and sudoku puzzles
Week 13: Revision
Please check that your mark for Quiz 1, Assignment and Quiz 2 have been recorded correctly by entering your 9 digit SID into the box below and then pressing the "Check marks" button.
Please note that any corrections must be made by Friday, June 5