Course specification
The current and official versions of the course specifications are available on the web at http://www.usq.edu.au/course/specification/current.
Please consult the web for updates that may occur during the year.

# MAT1101 Discrete Mathematics for Computing

 Semester 1, 2013 On-campus Toowoomba Units : 1 Faculty or Section : Faculty of Sciences School or Department : Maths and Computing Version produced : 21 July 2014

## Staffing

Examiner: Nicolas Jourdan
Moderator: Xiaohui Tao

## Other requisites

Current skills at the level of Queensland Senior Secondary School Studies Mathematics B or equivalent are recommended.

## Rationale

Discrete methods underlie the areas of data structures, computational complexity and the analysis of algorithms. Continuing advances in technology - particularly in applications of computing - have enhanced the importance of discrete (or finite) mathematics for understanding not only the foundations of computer science but also the basis on which computational solutions to a wide variety of applications problems rests.

## Synopsis

This course introduces the basic elements of discrete mathematics which provide a foundation for an understanding of algorithms and data structures used in computing. Topics covered include number systems, logic, relations, functions, induction, recursion, Boolean algebra and graph theory.

## Objectives

On successful completion of this course students will be able to:

1. demonstrate an understanding of how numeric and character data are stored in a computer;
2. demonstrate proficiency in converting simple algorithms into functional pseudo-code;
3. demonstrate proficiency with symbolic logic, in mathematical reasoning and the construction of proofs;
4. show familiarity with the basic notions of graphs and relationships.

## Topics

Description Weighting(%)
1. Computer representation of character and numeric data. Binary and hexadecimal system. ASCII code. Integer and floating point representations. 25.00
2. Functions and algorithms. Pseudo-code for binary/decimal and other conversions. Control structures for iteration and branching. Recursive functions. Proof by induction. 25.00
3. Truth tables and the laws of logic. Venn diagrams. Ordering and equivalence relationships. Digital circuits and Boolean algebra. Logical reduction and Karnaugh maps. 25.00
4. Graphs and trees. Eulerian and Hamiltonian graphs. Spanning trees. Dijkstra's and Prim's algorithms. Expression trees. Huffman codes. 25.00

## Text and materials required to be purchased or accessed

ALL textbooks and materials available to be purchased can be sourced from USQ's Online Bookshop (unless otherwise stated). (https://bookshop.usq.edu.au/bookweb/subject.cgi?year=2013&sem=01&subject1=MAT1101)

• Grossman, Peter 2009, Discrete Mathematics for Computing, 3rd edn, Palgrave MacMillan, Basingstoke, New York.
• A scientific calculator.
• All other study materials are available only from the course website which can be accessed through the USQStudyDesk.

## Reference materials

Reference materials are materials that, if accessed by students, may improve their knowledge and understanding of the material in the course and enrich their learning experience.
• Epp, S 2011, Discrete Mathematics with Applications, 4th edn, Brooks/Cole, Pacific Grove, Ca.
• Gersting, JL 2003, Mathematical Structures for Computer Science, 5th edn, WH Freeman, New York.
• Grimaldi, RP 2003, Discrete and Combinatorial Mathematics: an applied introduction, 5th edn, Addison-Wesley, Boston, Mass.
• Ross, KA & Wright, CRB 2003, Discrete Mathematics, 5th edn, Prentice Hall, Upper Saddle River, NJ.

Activity Hours
Assessments 30.00
Examinations 2.00
Lectures 26.00
Private Study 91.00
Tutorials 13.00

## Assessment details

Description Marks out of Wtg (%) Due Date Notes
ASSIGNMENT 1 30 20 28 Mar 2013
ASSIGNMENT 2 30 20 17 May 2013
2HR RESTRICTED EXAMINATION 100 60 End S1 (see note 1)

NOTES
1. Please refer to the Examination Timetable when it is published to confirm the examination date.

## Important assessment information

1. Attendance requirements:
It is the students' responsibility to attend and participate appropriately in all activities (such as lectures, tutorials, laboratories and practical work) scheduled for them, and to study all material provided to them or required to be accessed by them to maximise their chance of meeting the objectives of the course and to be informed of course-related activities and administration.

2. Requirements for students to complete each assessment item satisfactorily:
To complete each of the assessment items satisfactorily, students must obtain at least 50% of the marks available for each assessment item.

3. Penalties for late submission of required work:
If students submit assignments after the due date without (prior) approval of the examiner then a penalty of 5% of the total marks gained by the student for the assignment may apply for each working day late up to ten working days at which time a mark of zero may be recorded.

4. Requirements for student to be awarded a passing grade in the course:
To be assured of receiving a passing grade a student must achieve at least 50% of the total weighted marks available for the course.

5. Method used to combine assessment results to attain final grade:
The final grades for students will be assigned on the basis of the weighted aggregate of the marks obtained for each of the summative assessment items in the course.

6. Examination information:
The only materials that candidates may use in the restricted examination for this course are: writing materials (non-electronic and free from material which could give the student an unfair advantage in the examination); calculators which cannot hold textual information (i.e. no graphics or programmable calculators); One A4 sheet, written or typed on one or both sides with any material the student wishes to have. Students whose first language is not English, may, take an appropriate unmarked non-electronic translation dictionary (but not technical dictionary) into the examination. Dictionaries with any handwritten notes will not be permitted. Translation dictionaries will be subject to perusal and may be removed from the candidate's possession until appropriate disciplinary action is completed if found to contain material that could give the candidate an unfair advantage.

7. Examination period when Deferred/Supplementary examinations will be held:
Any Deferred or Supplementary examinations for this course will be held during the next examination period.

8. University Student Policies:
Students should read the USQ policies: Definitions, Assessment and Student Academic Misconduct to avoid actions which might contravene University policies and practices. These policies can be found at http://policy.usq.edu.au.

## Assessment notes

1. Students must retain a copy of each assignment submitted for assessment. This should be despatched to USQ within 24 hours of receipt of a request from the Examiner.

2. Students who, for medical, family/personal, or employment-related reasons, are unable to complete an assignment or to sit for an examination at the scheduled time may apply to defer an assessment in this course. Such a request must be accompanied by appropriate supporting documentation. One of the following temporary grades may be awarded IDS (Incomplete - Deferred Examination; IDM (Incomplete Deferred Make-up); IDB (Incomplete - Both Deferred Examination and Deferred Make-up).

3. In the normal course of events students should have access to e-mail and the internet for this course. This access is assumed in the running of the course. Alternative arrangements may be made in special circumstances on request.

4. The referencing system to be used in this course is supported by the Department. Information on this referencing system and advice on how to use it can be found in the course materials.