Note: This unit version is currently being edited and is subject to change!

MATH2069: Discrete Mathematics and Graph Theory (2019 - Semester 1)

Download UoS Outline

Unit: MATH2069: Discrete Mathematics and Graph Theory (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Intermediate
Faculty/School: School of Mathematics and Statistics
Unit Coordinator/s:
Session options: Semester 1
Versions for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: 6 credit points of Junior level Mathematics
Prohibitions: MATH2011, MATH2009, MATH2969
Brief Handbook Description: This unit introduces students to several related areas of discrete mathematics, which serve their interests for further study in pure and applied mathematics, computer science and engineering. Topics to be covered in the first part of the unit include recursion and induction, generating functions and recurrences, combinatorics, asymptotics and analysis of algorithms. Topics covered in the second part of the unit include Eulerian and Hamiltonian graphs, the theory of trees (used in the study of data structures), planar graphs, the study of chromatic polynomials (important in scheduling problems), maximal flows in networks, matching theory.
Assumed Knowledge: None.
Timetable: MATH2069 Timetable
T&L Activities: Lectures: Three 1 hour lectures, one 1 hour tutorial and one 1 hour practice class per week.

Practical Work:

Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.

(1) Maths/ Science Methods and Tools (Level 2)
1. Identify and use combinatorial objects involved in counting problems to solve them
2. Solve linear recurrence relations by using generating functions and characteristic equations identify Eulerian and Hamiltonian graphs
3. Apply special algorithms to find minimal walks in weighted graphs
4. Apply special algorithms to find spanning trees in graphs
5. Find chromatic numbers and chromatic polynomials of graphs.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Quiz 1 No 15.00 Week 5 1, 2,
2 Assignment No 10.00 Week 7 1,
3 Quiz 2 Yes 15.00 Week 11 3, 4,
4 Final Exam No 60.00 Exam Period 1, 2, 3, 4, 5,
Assessment Description: One 2 hour exam, assignments, quizzes (100%)

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 5 Assessment Due: Quiz 1
Week 7 Assessment Due: Assignment
Week 11 Assessment Due: Quiz 2
Exam Period Assessment Due: Final Exam

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Software Mid-Year 2016, 2017, 2018, 2019
Software/ Project Management 2019
Software 2015, 2016, 2017, 2018, 2019
Software / Arts 2015, 2016, 2017, 2018, 2019
Software / Commerce 2015, 2016, 2017, 2018, 2019
Software / Medical Science 2015, 2016, 2017
Software / Music Studies 2016, 2017
Software / Project Management 2015, 2016, 2017, 2018
Software / Science 2015, 2016, 2017, 2018, 2019
Software/Science (Health) 2018, 2019
Software / Law 2015, 2016, 2017, 2018, 2019
Software Engineering (till 2014) 2010, 2011, 2012, 2013, 2014
Software Engineering / Arts 2011, 2012, 2013, 2014
Software Engineering / Commerce 2010, 2011, 2012, 2013, 2014
Software Engineering / Medical Science 2011, 2012, 2013, 2014
Software Engineering / Project Management 2012, 2013, 2014
Software Engineering / Science 2011, 2012, 2013, 2014
Software Engineering / Law 2010, 2011, 2012, 2013, 2014
Information Technology (Computer Science)/Arts 2012, 2013, 2014
Information Technology (Computer Science) / Commerce 2012, 2013, 2014
Information Technology (Computer Science) / Medical Science 2012, 2013, 2014
Information Technology (Computer Science) / Science 2012, 2013, 2014
Information Technology (Computer Science) / Law 2012, 2013, 2014
Information Technology (Information Systems)/Arts 2012, 2013, 2014
Information Technology (Information Systems) / Commerce 2012, 2013, 2014
Information Technology (Information Systems) / Medical Science 2012, 2013, 2014
Information Technology (Information Systems) / Science 2012, 2013, 2014
Information Technology (Information Systems) / Law 2012, 2013, 2014
Software/Science (Medical Science Stream) 2018, 2019
Bachelor of Computer Science and Technology 2015, 2016, 2017
Bachelor of Computer Science and Technology (Advanced) 2015, 2016, 2017
Bachelor of Computer Science and Technology (Computer Science) 2014 and earlier 2010, 2011, 2012, 2013, 2014
Bachelor of Computer Science and Technology (Computer Science)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science and Technology (Information Systems) 2014 and earlier 2011, 2012, 2013, 2014
Bachelor of Computer Science and Technology (Information Systems)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science & Tech. Mid-Year 2016, 2017
Aeronautical Engineering / Science 2011, 2012, 2013, 2014
Aeronautical Engineering (Space) / Science 2011, 2012, 2013, 2014
Biomedical Engineering / Science 2013, 2014
Chemical & Biomolecular Engineering / Science 2011, 2012, 2013, 2014
Civil Engineering / Science 2011, 2012, 2013, 2014
Electrical Engineering (Bioelectronics) / Science 2011, 2012
Electrical Engineering / Science 2011, 2012, 2014
Electrical Engineering (Computer) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Science 2011, 2012, 2013, 2014
Aeronautical / Science 2015, 2016, 2017
Aeronautical (Space) / Science 2015
Biomedical /Science 2015, 2016, 2017
Chemical & Biomolecular / Science 2015, 2016, 2017
Civil / Science 2015, 2016, 2017
Electrical / Science 2015, 2016, 2017
Electrical (Computer) / Science 2015
Electrical (Power) / Science 2015
Electrical (Telecommunications) / Science 2015
Mechanical / Science 2015, 2016, 2017
Mechanical (Space) / Science 2015
Mechatronic / Science 2015, 2016, 2017
Mechatronic (Space) / Science 2015
Mechanical Engineering (Biomedical) / Science 2011, 2012
Mechanical Engineering / Science 2011, 2012, 2013, 2014
Mechanical Engineering (Space) / Science 2011, 2012, 2013, 2014
Mechatronic Engineering / Science 2011, 2012, 2013, 2014
Mechatronic Engineering (Space) / Science 2011, 2012, 2013, 2014
Project Engineering and Management (Civil) / Science 2011
Bachelor of Information Technology 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Arts 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Commerce 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Medical Science 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Science 2015, 2016, 2017
Bachelor of Information Technology (Computer Science) 2014 and earlier 2011, 2012, 2013, 2014
Bachelor of Information Technology (Information Systems) 2014 and earlier 2011, 2012, 2013, 2014
Bachelor of Information Technology/Bachelor of Laws 2015, 2016, 2017
Bachelor of Project Management (Built Environment) 2018, 2016, 2017
Bachelor of Project Management (Civil Engineering Science) 2018, 2016, 2017
Bachelor of Project Management (Software) 2018, 2016, 2017
Bachelor of Project Management (Built Environment) Mid-Year 2016, 2017, 2018
Bachelor of Project Management (Civil Engineering Science) Mid-Year 2016, 2017, 2018
Bachelor of Project Management (Software) Mid-Year 2016, 2017, 2018
Flexible First Year (Stream A) / Science 2012

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
(1) Maths/ Science Methods and Tools (Level 2) No 100%

These goals are selected from Engineering & IT Graduate Outcomes Table 2018 which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 2018 for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.