Unit Guide

General Information

Unit convenor and teaching staff	Unit convenor and teaching staff Other Staff Gerry Myerson gerry.myerson@mq.edu.au Contact via gerry.myerson@mq.edu.au Unit Convenor Ross Moore ross.moore@mq.edu.au Contact via ross.moore@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:

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.
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.

Assessment Tasks

Name	Weighting	Due
Five assignments	20%	see unit website
1 Project	20%	see unit website
Final examination	60%	University Examination Period
online quizzes	0%	see unit website

Five assignments

Due: see unit website
Weighting: 20%

For specific details, see the unit website.

On successful completion you will be able to:

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.
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.

1 Project

Due: see unit website
Weighting: 20%

RSA Project. Consult the unit website.

On successful completion you will be able to:

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
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.

Final examination

Due: University Examination Period
Weighting: 60%

See the unit website concerning the “expected participation" required for an expectation of achieving a satisfactory grade overall.

On successful completion you will be able to:

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.
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.

online quizzes

Due: see unit website
Weighting: 0%

These quizzes are effectively home-work, but are “compulsory”.

On successful completion you will be able to:

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
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.

Delivery and Resources

Classes

Lectures: you should attend two hours of each lecture stream each week, making a total of four hours.

Tutorials: you should attend one tutorial each week.

Practicals: you should attend one practical each week.

Workshops: available for students wanting to see more examples and ask further questions. Attendance is strongly recommended.

Online lecture notes

Recommended Texts and/or Materials

Grimaldi, Discrete and Combinatorial Mathematics (Addison-Wesley-Longman 2003)
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.

Technology Used and Required

Students are expected to have access to an internet enabled computer with a web browser and Adobe Reader software. Several areas of the university provide wireless access for portable computers. There are computers for student use in the Library and in the Numeracy Centre (C5A 255).

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	ALGEBRA & GRAPH THEORY	LANGUAGES & MACHINES	TASK DUE
1	23/02/2015	Complex numbers: Cooper, Chen	Languages
2	02/03/2015		Introduction to finite-state machines (FSMs)
3	09/03/2015	Introduction to matrix theory: Cooper, Chen	Reduction of FSMs	Q1
4	16/03/2015		Non-deterministic finite-state acceptors (FSAs)	A1 Q2
5	23/03/2015	Revision of counting techniques: Cooper, Chen	FSAs and regular languages	Q3
6	30/03/2015	Generating functions	Turing machines	A2 Q4
MID-SESSION BREAK
7	20/04/2015	Generating functions	Turing machines	FSA
8	27/04/2015	Recurrence relations	Extended Turing machines	A3
9	04/05/2015		The Busy Beaver and Halting problems	Q5
10	11/05/2015		Integers mod m and cryptography	A4
11	18/05/2015	Graph algorithms: Cooper, Chen	Polynomial codes	Q6
12	25/05/2015		Matrix codes	A5
13	01/06/2015	Revision		Q7

This table is a rough guide to the timing of the material in DMTH237. Please note that the order and weeks of topics is likely to change. The assignment, test and quiz dates are fixed. Once complete, this table may not be updated during semester.

Attendance at lectures and tutorials is the only sure way to find out the where the schedule of topics is up to.

Policies and Procedures

Macquarie University policies and procedures are accessible from Policy Central. Students should be aware of the following policies in particular with regard to Learning and Teaching:

Academic Honesty Policy http://mq.edu.au/policy/docs/academic_honesty/policy.html

Assessment Policy http://mq.edu.au/policy/docs/assessment/policy.html

Grading Policy http://mq.edu.au/policy/docs/grading/policy.html

Grade Appeal Policy http://mq.edu.au/policy/docs/gradeappeal/policy.html

Grievance Management Policy http://mq.edu.au/policy/docs/grievance_management/policy.html

Disruption to Studies Policy http://www.mq.edu.au/policy/docs/disruption_studies/policy.html The Disruption to Studies Policy is effective from March 3 2014 and replaces the Special Consideration Policy.

In addition, a number of other policies can be found in the Learning and Teaching Category of 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/support/student_conduct/

Results

Results shown in iLearn, 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.

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

IT Help

For help with University computer systems and technology, visit http://informatics.mq.edu.au/help/.

When using the University's IT, you must adhere to the Acceptable Use 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

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.

Assessment task

1 Project

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 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.

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

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.

Assessment tasks

Five assignments
1 Project
Final examination

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

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.

Assessment tasks

Five assignments
1 Project
Final examination

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

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.

Assessment tasks

Five assignments
1 Project
Final examination

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

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.
Construct sustained logical, clearly presented and justified mathematical arguments incorporating deductive reasoning, particularly in areas concerning how computer programs work and can be used.
Expressing yourself clearly and logically in writing.

Assessment tasks

Five assignments
Final examination

Changes from Previous Offering

Tutorials and Practical Sessions commence in Week 1. This is primarily to give those students that have entered the DMTH237 via the mathematics pathway (MATH135, MATH136, etc.) rather than the usual prerequisite unit DMTH137 for Computer Science & Information Systems students. The material for 1st week tutorials and Practicals is revision of the basic topics: Logic, Set Theory, Counting methods.

extra requirements

In order to obtain a passing grade in this unit, students are required to demonstrate their mastery of the required basic skills and techniques by passing all seven (7) on-line quizzes. Students who do not meet this requirement will have their grade capped at F 49.

Satisfactory performance on supervised assessment tasks, such as tests and the final exam, is necessary to pass this unit. If there is a significant difference between a student's marks on supervised assessment tasks and on unsupervised assessment tasks, the scaling of these tasks may be adjusted when determining the final grade, to reflect more appropriately that student's performance on supervised tasks.

Changes since First Published

Date	Description
12/03/2015	Updated old links (to 2014 unit website) to the correct 2015 unit website pages. 3 instances on pages 3 & 4 in the table of Assessments.