MATH 2004 Discrete Structures and Complexity

This is an archived copy of the 2021-2022 catalog. To access the most recent version of the catalog, please visit https://hbook.westernsydney.edu.au.

Credit Points 10

Legacy Code 300699

Coordinator Volker Gebhardt Opens in new window

Description The fact that computers work at all in the way they do is due to the formal mathematical structure that is used in their design. The same holds for establishing important matters such as the reliability of our computer networks. This unit presents, in their computing context, a range of mathematical concepts that are essential for understanding a number of topics concerning computers: the ways they work, they ways they interact, and the ways we interact with them.

School Computer, Data & Math Sciences

Discipline Mathematics

Student Contribution Band HECS Band 1 10cp

Check your HECS Band contribution amount via the Fees page.

Level Undergraduate Level 2 subject

Pre-requisite(s) MATH 1028

Incompatible Subjects MATH 1006 - Discrete Mathematics

Restrictions Students must be enrolled in 3639 Bachelor of Information and Communications Technology or the following double degrees 3654, 3655, 3656, 3657, 3661

Assumed Knowledge

Basic programming such as that in 300580 - Programming Fundamentals.

Learning Outcomes

On successful completion of this subject, students should be able to:
  1. Appreciate some of the roles that mathematics plays in computing;
  2. Recognise a function, decide whether a given function is one-to-one or onto, and perform elementary manipulations with functions;
  3. Decide the truth of logical statements involving connectives, and simplify logical expressions using the laws of logic and truth tables;
  4. Describe the connections between basic set operations and logic connectives;
  5. Describe simple and directed graphs, use concepts such as "path", and find minimal spanning trees
  6. Understand the differences between logarithmic, linear, quadratic and exponential algorithms and perform basic complexity analysis on algorithms such as simple sorting algorithms.
  7. Appreciate the relevance of the content to computing.

Subject Content

The content of the subject is driven by several computing questions, broken down into modules. Each module consists of an issue in computing that requires certain mathematics to address. The modules, and the mathematics they address, are:
Module 1: Functions, what is and isn't a function, one-to-one and onto functions, representing functions.
Module 2: The way computers "think": logic, and how this relates to sets.
Module 3: Networks and their structure: graphs, spanning trees and matrices.
Module 4: Algorithm efficiency: the analysis of some simple algorithms. Comparisons of various algorithms, why complexity is important. Revision of relevant counting material.

Teaching Periods

Structures that include subject