Students

DMTH237 – Discrete Mathematics II

2019 – S1 Day

General Information

Download as PDF
Unit convenor and teaching staff Unit convenor and teaching staff Unit Convenor & Lecturer
Ross Moore
ross.moore@mq.edu.au
Contact via 9850 8955
12 Wally's Walk Office 7.34
Tuesdays 11:00-1:00pm, 3:00-5:00pm
Lecturer
Frank Valckenborgh
frank.valckenborgh@mq.edu.au
Contact via 9850 8945
12 Wally's Walk Office 6.13
Tuesdays 11:00-1:00pm, 3:00-5:00pm
Frank Schoenig
frank.schoenig@mq.edu.au
Credit points Credit points
3
Prerequisites Prerequisites
DMTH137 or MATH133 or MATH136
Corequisites Corequisites
Co-badged status Co-badged status
Unit description Unit description
The purpose of this unit is to give a grounding in discrete mathematics. It is important preparation for both theoretical computing and abstract algebra. In particular, the unit: explores the concept of computability, and the measures of computational complexity and finite state machines; studies recurrence relations and generating functions; provides an introduction to matrices with applications to systems of linear equations and vectors; applies graph theory to a range of problems; and examines a variety of error-correcting and public-key cryptography codes.

Important Academic Dates

Information about important academic dates including deadlines for withdrawing from units are available at https://www.mq.edu.au/study/calendar-of-dates

Learning Outcomes

On successful completion of this unit, you will be able to:

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

General Assessment Information

Attendance at, and reasonable engagement in, Small Group Teaching Activities (SGTA) is regarded as being compulsory. Participation may be assessed by instructors via rosters and/or observation of students' work during classes. Attendance and reasonable engagement in the class activities in at least 8 out of 12 classes is highly recommended to achieve a passing grade in the unit.

ATTENDANCE and PARTICIPATION: Please contact the Unit Convenor as soon as possible if you have difficulty attending and participating in any classes. There may be alternatives available to make up the work. If there are circumstances that mean you miss a class, you can apply for a Special Consideration via  ask.mq.edu.au.

ONLINE QUIZZES – HURDLE: The online quizzes may be attempted as many times as necessary during the teaching period. There will be no additional make-up opportunity once the teaching period has finished. These are hurdle requirements.

LATE SUBMISSION of WORK: All assignments and assessment tasks must be submitted by the official due date and time. No marks will be given for late work unless an extension has been granted following a successful application for Special Consideration. Please contact the Unit Convenor for advice as soon as you become aware that you may have difficulty meeting any of the assignment deadlines.

FINAL EXAM POLICY: You are advised that it is Macquarie University policy not to set early examinations for individuals or groups of students. All students are expected to ensure that they are available until the end of the teaching semester, that is, the final day of the official examination period. The only excuse for not sitting an examination at the designated time is because of documented illness or unavoidable disruption. In these special circumstances, you may apply for special consideration via ask.mq.edu.au.

If you receive SPECIAL CONSIDERATION for the final exam, a supplementary exam will be scheduled. By making a special consideration application for the final exam you are declaring yourself available for a resit during the supplementary examination period and will not be eligible for a second special consideration approval based on pre-existing commitments. Please ensure you are familiar with the policy prior to submitting an application. You can check the supplementary exam information page on FSE101 in iLearn (bit.ly/FSESupp) for dates, and approved applicants will receive an individual notification one week prior to the exam with the exact date and time of their supplementary examination.

If you apply for Special Consideration for the final examination, you must make yourself available for the Supplementary Examination as organised by the Faculty of Science & Engineering. If you are not available at that time, there is no guarantee that an additional examination time will be offered. Specific examination dates and times will be determined at a later date.

Assessment Tasks

Name Weighting Hurdle Due
Three assignments 30% No Wednesday weeks 5, 9, 12
FSA Project 20% No Wednesday 1 May
Final examination 50% No University Examination Period
Online Quizzes 0% Yes weeks 3, 4, 6, 7, 8, 10, 13

Three assignments

Due: Wednesday weeks 5, 9, 12
Weighting: 30%

For specific details, see the unit iLearn site.
On successful completion you will be able to:
  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

FSA Project

Due: Wednesday 1 May
Weighting: 20%

FSA Project. Consult the unit iLearn website. This project is submitted online and immediate feedback is given. Update your submitted solutions as frequently as necessary to correctly perform the required programming task.
On successful completion you will be able to:
  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Final examination

Due: University Examination Period
Weighting: 50%

See the unit iLearn site concerning the “expected participation" required for an expectation of achieving a satisfactory grade overall.
On successful completion you will be able to:
  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Online Quizzes

Due: weeks 3, 4, 6, 7, 8, 10, 13
Weighting: 0%
This is a hurdle assessment task (see assessment policy for more information on hurdle assessment tasks)

The quizzes are competency tests to ensure that all students who pass this unit possess certain basic skills. You can repeat them as many times as it takes in order to pass. 

You must pass all 7 quizzes to pass this unit.
On successful completion you will be able to:
  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Delivery and Resources

Textbooks and online resources

There is no single required text for this unit. Some of the topics are covered in the text used with DMTH137:

  • Discrete Mathematics and Its Applications by K.H. Rosen; 7th edition, McGraw-Hill
  • Discrete Mathematics and Its Applications by K.H. Rosen; 8th edition, McGraw-Hill (2019)

The following link to sets of online lecture notes as used in previous years, for DMTH237. These cover all the material, and provide exercises and examples:

You may download and study these, from the DMTH237 iLearn site, to get different view-points and explanations of the same material.  The online notes are intended primarily as a source of reference. These are not intended to be treated as the only source for learning.

Free Online Textbooks

The following online texts contain material mostly studied in DMTH137, with some of the Algebra topics from this unit. They are a good source for alternative viewpoints, worked examples and exercises with some solutions.

These are particularly recommended for students who have not studied DMTH137 to do independent study. Lecture slides from a previous year's offering of DMTH137 can be studied or used for revision.

Recommended reading

  • Grimaldi, Discrete and Combinatorial Mathematics (Addison-Wesley-Longman 2003)
  • JL Gersting, Mathematical Structures for Computer Science (Freeman, 7th edition 2014)
  • RL Graham, DE Knuth, O Patashnik, Concrete mathematics: a foundation for computer science (Addison-Wesley 1994)
  • WD Hillis, The pattern on the stone. The simple ideas that make computers work. (Weidenfeld, Nicolson 1998)
  • A Hodges, Alan Turing: the enigma (Vintage 1992)
  • DR Hofstadter, Godel, Escher, Bach: an eternal braid (1979) The Harvester Press
  • DE Knuth, The art of computer programming - Fundamental algorithms (1973) Addison-Wesley
  • M Minsky, Computation: finite and infinite machines (1967) Prentice-Hall
  • S Singh, The Code Book (1999) Fourth Estate

These and similar texts are available in the Library. Other similar texts are available in the Library, and for reference in the Numeracy Centre (E7B G.88)

Difficulties with your home computer or internet connection do not constitute a reasonable excuse for lateness of, or failure to submit, assessment tasks.

Unit Schedule

WEEK

BEGINNING

V-strand: ALGEBRA

M-strand: LANGUAGES & MACHINES

TASK DUE

1

25/02/2019

Complex numbers

Languages

 

2

04/03/2019

Linear systems and matrices

Introduction to finite-state machines (FSMs)

 

3

11/03/2019

 

Reduction of FSMs

Q1

4

18/03/2019

 

Non-deterministic finite-state acceptors (FSAs)

Q2

5

25/03/2019

Counting Inclusion–Exclusion

FSAs and regular languages

A1

6

01/04/2019

Counting (cont'd)  Generating Functions

 

Q3

7

08/04/2019

 

Turing machines

Q4

MID-SESSION BREAK (incl. EASTER)

8

29/04/2019

Recurrence relations

Turing machines

FSA Q5

9

06/05/2019

 

Extended Turing machines

A2

10

13/05/2019

Graph algorithms

The Busy Beaver and Halting problems

Q6

11

20/05/2019

 

Integers mod m and cryptography

 

12

27/05/2019

 

Polynomial codes

A3

13

03/06/2019

Revision  (provided all topics have been completed)

Q7

This table is a rough guide to the timing of the delivery of material in DMTH237. The assignment, project and quiz dates are fixed.

Links in the above table are to files available only through the Unit's iLearn site.

Policies and Procedures

Macquarie University policies and procedures are accessible from Policy Central (https://staff.mq.edu.au/work/strategy-planning-and-governance/university-policies-and-procedures/policy-central). Students should be aware of the following policies in particular with regard to Learning and Teaching:

Undergraduate students seeking more policy resources can visit the Student Policy Gateway (https://students.mq.edu.au/support/study/student-policy-gateway). It is your one-stop-shop for the key policies you need to know about throughout your undergraduate student journey.

If you would like to see all the policies relevant to Learning and Teaching visit Policy Central (https://staff.mq.edu.au/work/strategy-planning-and-governance/university-policies-and-procedures/policy-central).

Student Code of Conduct

Macquarie University students have a responsibility to be familiar with the Student Code of Conduct: https://students.mq.edu.au/study/getting-started/student-conduct​

Results

Results published on platform other than eStudent, (eg. iLearn, Coursera etc.) or released directly by your Unit Convenor, are not confirmed as they are subject to final approval by the University. Once approved, final results will be sent to your student email address and will be made available in eStudent. For more information visit ask.mq.edu.au or if you are a Global MBA student contact globalmba.support@mq.edu.au

Student Support

Macquarie University provides a range of support services for students. For details, visit http://students.mq.edu.au/support/

Learning Skills

Learning Skills (mq.edu.au/learningskills) provides academic writing resources and study strategies to improve your marks and take control of your study.

Student Services and Support

Students with a disability are encouraged to contact the Disability Service who can provide appropriate help with any issues that arise during their studies.

Student Enquiries

For all student enquiries, visit Student Connect at ask.mq.edu.au

If you are a Global MBA student contact globalmba.support@mq.edu.au

IT Help

For help with University computer systems and technology, visit http://www.mq.edu.au/about_us/offices_and_units/information_technology/help/. 

When using the University's IT, you must adhere to the Acceptable Use of IT Resources Policy. The policy applies to all who connect to the MQ network including students.

Graduate Capabilities

Creative and Innovative

Our graduates will also be capable of creative thinking and of creating knowledge. They will be imaginative and open to experience and capable of innovation at work and in the community. We want them to be engaged in applying their critical, creative thinking.

This graduate capability is supported by:

Learning outcomes

  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Capable of Professional and Personal Judgement and Initiative

We want our graduates to have emotional intelligence and sound interpersonal skills and to demonstrate discernment and common sense in their professional and personal judgement. They will exercise initiative as needed. They will be capable of risk assessment, and be able to handle ambiguity and complexity, enabling them to be adaptable in diverse and changing environments.

This graduate capability is supported by:

Learning outcomes

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Commitment to Continuous Learning

Our graduates will have enquiring minds and a literate curiosity which will lead them to pursue knowledge for its own sake. They will continue to pursue learning in their careers and as they participate in the world. They will be capable of reflecting on their experiences and relationships with others and the environment, learning from them, and growing - personally, professionally and socially.

This graduate capability is supported by:

Learning outcomes

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Discipline Specific Knowledge and Skills

Our graduates will take with them the intellectual development, depth and breadth of knowledge, scholarly understanding, and specific subject content in their chosen fields to make them competent and confident in their subject or profession. They will be able to demonstrate, where relevant, professional technical competence and meet professional standards. They will be able to articulate the structure of knowledge of their discipline, be able to adapt discipline-specific knowledge to novel situations, and be able to contribute from their discipline to inter-disciplinary solutions to problems.

This graduate capability is supported by:

Learning outcomes

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Critical, Analytical and Integrative Thinking

We want our graduates to be capable of reasoning, questioning and analysing, and to integrate and synthesise learning and knowledge from a range of sources and environments; to be able to critique constraints, assumptions and limitations; to be able to think independently and systemically in relation to scholarly activity, in the workplace, and in the world. We want them to have a level of scientific and information technology literacy.

This graduate capability is supported by:

Learning outcomes

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Problem Solving and Research Capability

Our graduates should be capable of researching; of analysing, and interpreting and assessing data and information in various forms; of drawing connections across fields of knowledge; and they should be able to relate their knowledge to complex situations at work or in the world, in order to diagnose and solve problems. We want them to have the confidence to take the initiative in doing so, within an awareness of their own limitations.

This graduate capability is supported by:

Learning outcomes

  • Able to appreciate what kinds of problems are capable of being solved with a computer; in particular appreciating that there are some problems that are logically intractable.
  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Effective Communication

We want to develop in our students the ability to communicate and convey their views in forms effective with different audiences. We want our graduates to take with them the capability to read, listen, question, gather and evaluate information resources in a variety of formats, assess, write clearly, speak effectively, and to use visual communication and communication technologies as appropriate.

This graduate capability is supported by:

Learning outcomes

  • Expressing yourself clearly and logically in writing.
  • Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Engaged and Ethical Local and Global citizens

As local citizens our graduates will be aware of indigenous perspectives and of the nation's historical context. They will be engaged with the challenges of contemporary society and with knowledge and ideas. We want our graduates to have respect for diversity, to be open-minded, sensitive to others and inclusive, and to be open to other cultures and perspectives: they should have a level of cultural literacy. Our graduates should be aware of disadvantage and social justice, and be willing to participate to help create a wiser and better society.

This graduate capability is supported by:

Learning outcome

  • Demonstrate a well-developed knowledge of the principles, concepts and mathematical techniques, particularly as applied to problems requiring or applicable to computational methods and techniques. Solving problems, including: - formulating a precise mathematical question from a "real world" problem; - identifying and applying appropriate mathematical or computational techniques.

Assessment tasks

  • Three assignments
  • FSA Project
  • Final examination
  • Online Quizzes

Changes since First Published

Date Description
12/02/2019 The SGTA classes are no longer considered as a Hurdle requirement for this 200-level unit. With 7 online quizzes already as hurdles, ensuring a level of on-going participation, it is asking too much of students for the SGTAs to also have a Hurdle aspect. This has involved changes in the Assessment section(s).