MAT1101 Discrete Mathematics for Computing
Semester 1, 2012 Oncampus Toowoomba  
Units :  1 
Faculty or Section :  Faculty of Sciences 
School or Department :  Maths and Computing 
Version produced :  30 December 2013 
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:
 demonstrate an understanding of how numeric and character data are stored in a computer;
 demonstrate proficiency in converting simple algorithms into functional pseudocode;
 demonstrate proficiency with symbolic logic, in mathematical reasoning and the construction of proofs;
 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. Pseudocode 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=2012&sem=01&subject1=MAT1101)
Please contact us for alternative purchase options from USQ Bookshop. (https://bookshop.usq.edu.au/contact/)

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

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, AddisonWesley, Boston, Mass.

Ross, KA & Wright, CRB 2003, Discrete Mathematics, 5th edn, Prentice Hall, Upper Saddle River, NJ.
Student workload requirements
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  30 Mar 2012  
ASSIGNMENT 2  30  20  18 May 2012  
2HR RESTRICTED EXAMINATION  100  60  End S1  (see note 1) 
NOTES
 Please refer to the Examination Timetable when it is published to confirm the examination date.
Important assessment information

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 courserelated activities and administration. 
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. 
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. 
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. 
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. 
Examination information:
The only materials that candidates may use in the restricted examination for this course are: writing materials (nonelectronic 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 nonelectronic 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. 
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. 
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

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.

Students who, for medical, family/personal, or employmentrelated 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 Makeup); IDB (Incomplete  Both Deferred Examination and Deferred Makeup).

In the normal course of events students should have access to email 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.

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.