MATH 2004 Discrete Structures and Complexity
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 subject 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
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
Basic programming such as that in 300580 - Programming Fundamentals.
- Appreciate some of the roles that mathematics plays in computing;
- Recognise a function, decide whether a given function is one-to-one or onto, and perform elementary manipulations with functions;
- Decide the truth of logical statements involving connectives, and simplify logical expressions using the laws of logic and truth tables;
- Describe the connections between basic set operations and logic connectives;
- Describe simple and directed graphs, use concepts such as "path", and find minimal spanning trees
- Understand the differences between logarithmic, linear, quadratic and exponential algorithms and perform basic complexity analysis on algorithms such as simple sorting algorithms.
- Appreciate the relevance of the content to computing.
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.