Skip to menu Skip to content Skip to footer
Course profile

Graph Theory & Design Theory (MATH3301)

Study period
Sem 2 2024
Location
St Lucia
Attendance mode
In Person

Course overview

Study period
Semester 2, 2024 (22/07/2024 - 18/11/2024)
Study level
Undergraduate
Location
St Lucia
Attendance mode
In Person
Units
2
Administrative campus
St Lucia
Coordinating unit
Mathematics & Physics School

Various topics in Graph Theory including a selection of topics from extremal graphs, connectivity, network flows, planarity, graph colouring, graph factors and factorisations. Various topics in Design Theory including a selection of topics from balanced incomplete block designs, transversal and group divisible designs, pairwise balanced designs, orthogonal arrays and Latin squares.

This course is concerned with graph theory and design theory, and should allow students subsequently to read further in these areas, and to apply their knowledge of graph theory and design theory to other appropriate fields.

Graph theory and design theory are branches of the wide-ranging field known as combinatorics. They have applications in many different areas, including parts of computer science and operations research. The focus of this course is on theoretical aspects of graph theory and design theory.

Course requirements

Assumed background

The essential background for this subject is MATH2302.ᅠ

Prerequisites

You'll need to complete the following courses before enrolling in this one:

MATH2302

Incompatible

You can't enrol in this course if you've already completed the following:

MATH7331 (co-taught).

Jointly taught details

This course is jointly-taught with:

MATH3301 and MATH7331 are co-badged courses and will share learning activities. MATH7331 will have some differences in assessment to evaluate students at Level 9 (Masters) of the Australian Qualifications Framework.

Course contact

Course staff

Lecturer

Timetable

The timetable for this course is available on the UQ Public Timetable.

Additional timetable information

Monday 7thᅠ of October is a public holiday. There will be no classes on that day.

All classes will be conducted on campus. Consult your personal timetable for times and locations. Students are expected to attend these sessions in person unless they have a valid reason for being unable to attend (such as illness).

Important: if you are ill, then do not attend any classes in person. Alternative arrangements can be organised – consult Blackboard for details. 

Aims and outcomes

By the end of the semester, students should have sufficient understanding and knowledge of graph theory and design theory to

(i) read and understand most undergraduate monographs in the area;

(ii) solveᅠtheoretical problemsᅠin graph theory and design theory.

Learning outcomes

After successfully completing this course you should be able to:

LO1.

understand the definition of and some construction techniques for balanced incomplete block designs.

LO2.

understand the definitions of, and connections between, pairwise balanced designs, group divisible designs, transversal designs, orthogonal arrays and Latin squares.

LO3.

understand important concepts in graph theory such as graph connectivity, extremal graphs, graph factorisation and planarity.

LO4.

understand the concept of networks, flows in networks, and some algorithms used to calculate maximum flows.

LO5.

appreciate some of the connections between graph theory and design theory.

Assessment

Assessment summary

Category Assessment task Weight Due date
Tutorial/ Problem Set Assignment 1 5%

16/08/2024 1:00 pm

Examination In-semester Examination
  • Identity Verified
  • In-person
0% or 36%

29/08/2024 11:50 am

Tutorial/ Problem Set Assignment 2 5%

11/10/2024 1:00 pm

Examination Final Exam
  • Identity Verified
  • In-person
54% or 90%

End of Semester Exam Period

2/11/2024 - 16/11/2024

Assessment details

Assignment 1

Mode
Written
Category
Tutorial/ Problem Set
Weight
5%
Due date

16/08/2024 1:00 pm

Task description

Assignment 1 requires you to answer a set of questions and submit your written solutions. Solutions will be marked for correctness, accuracy, appropriateness of mathematical techniques, clarity of presentation and quality of expression, and depth of understanding demonstrated.

Submission guidelines

Assignment 1 must be submitted electronically as a single pdf file. Ensure that your name, student number and tutorial group number appear on the first page of your submission. Make sure that your pdf file is legible and that the file size is not excessive. Use the assignment submission link in Blackboard to submit the pdf file. Pay careful attention to the general university guidelines on plagiarism in Section 6. You are welcome to work in small groups, particularly in class. However, assignments must be completed individually, so everything you submit must be your own work. Inappropriate copying or excessive collaboration will be taken very seriously.

Deferral or extension

You may be able to apply for an extension.

The maximum extension allowed is 7 days. Extensions are given in multiples of 24 hours.

As solutions will be released 7 days after the due date, extensions longer than 7 days cannot be granted. No assessment can be accepted after solutions are released. If you have extenuating circumstances, then you should contact the course coordinator about an exemption. See ADDITIONAL ASSESSMENT INFORMATION for extension and deferred examination information relating to this assessment item.

Late submission

A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.

You are required to submit assessable items on time. If you fail to meet the submission deadline for any assessment item a penalty of 10% of the maximum possible mark allocated for the assessment item will be deducted per day for up to 7 calendar days, at which point any submission will not receive any marks unless an extension has been approved. Each 24 hour block is recorded from the time the submission is due.

In-semester Examination

  • Identity Verified
  • In-person
Mode
Written
Category
Examination
Weight
0% or 36%
Due date

29/08/2024 11:50 am

Other conditions
Time limited.

See the conditions definitions

Task description

In-semester exam held in class 10am - 11:50am on Thursday 29 August.

Exam details

Planning time no planning time minutes
Duration 110 minutes
Calculator options

(In person) Casio FX82 series or UQ approved , labelled calculator only

Open/closed book Closed Book examination - no written materials permitted
Exam platform Paper based
Invigilation

Invigilated in person

Submission guidelines

Deferral or extension

You may be able to defer this exam.

See ADDITIONAL ASSESSMENT INFORMATION for extension and deferred examination information relating to this assessment item.

Assignment 2

Mode
Written
Category
Tutorial/ Problem Set
Weight
5%
Due date

11/10/2024 1:00 pm

Task description

Assignment 2 requires you to answer a set of questions and submit your written solutions. Solutions will be marked for correctness, accuracy, appropriateness of mathematical techniques, clarity of presentation and quality of expression, and depth of understanding demonstrated.

Submission guidelines

Assignment 2 must be submitted electronically as a single pdf file. Ensure that your name, student number and tutorial group number appear on the first page of your submission. Make sure that your pdf file is legible and that the file size is not excessive. Use the assignment submission link in Blackboard to submit the pdf file. Pay careful attention to the general university guidelines on plagiarism in Section 6. You are welcome to work in small groups, particularly in class. However, assignments must be completed individually, so everything you submit must be your own work. Inappropriate copying or excessive collaboration will be taken very seriously.

Deferral or extension

You may be able to apply for an extension.

The maximum extension allowed is 7 days. Extensions are given in multiples of 24 hours.

As solutions will be released 7 days after the due date, extensions longer than 7 days cannot be granted. No assessment can be accepted after solutions are released. If you have extenuating circumstances, then you should contact the course coordinator about an exemption. See ADDITIONAL ASSESSMENT INFORMATION for extension and deferred examination information relating to this assessment item.

Late submission

A penalty of 10% of the maximum possible mark will be deducted per 24 hours from time submission is due for up to 7 days. After 7 days, you will receive a mark of 0.

You are required to submit assessable items on time. If you fail to meet the submission deadline for any assessment item a penalty of 10% of the maximum possible mark allocated for the assessment item will be deducted per day for up to 7 calendar days, at which point any submission will not receive any marks unless an extension has been approved. Each 24 hour block is recorded from the time the submission is due.

Final Exam

  • Identity Verified
  • In-person
Mode
Written
Category
Examination
Weight
54% or 90%
Due date

End of Semester Exam Period

2/11/2024 - 16/11/2024

Other conditions
Time limited.

See the conditions definitions

Task description

The final examination in this course will be held during the end-of-semester examination period. It will be an in-person exam held on campus.

Exam details

Planning time 10 minutes
Duration 120 minutes
Calculator options

(In person) Casio FX82 series or UQ approved , labelled calculator only

Open/closed book Closed Book examination - no written materials permitted
Exam platform Paper based
Invigilation

Invigilated in person

Submission guidelines

Deferral or extension

You may be able to defer this exam.

See ADDITIONAL ASSESSMENT INFORMATION for extension and deferred examination information relating to this assessment item.

Course grading

Full criteria for each grade is available in the Assessment Procedure.

Grade Cut off Percent Description
1 (Low Fail) 1 -

Absence of evidence of achievement of course learning outcomes.

Course grade description: To achieve a grade of 1, a student must achieve an overall mark of less than 20%.

2 (Fail) 20 -

Minimal evidence of achievement of course learning outcomes.

Course grade description: To achieve a grade of 2, a student must achieve an overall mark of at least 20%, and not meet the requirements for a higher grade.

3 (Marginal Fail) 45 -

Demonstrated evidence of developing achievement of course learning outcomes

Course grade description: To achieve a grade of 3, a student must achieve an overall mark of at least 45% and not meet the requirements for a higher grade.

4 (Pass) 50 -

Demonstrated evidence of functional achievement of course learning outcomes.

Course grade description: To achieve a grade of 4, a student must achieve an overall mark of at least 50% and not meet the requirements for a higher grade.

5 (Credit) 65 -

Demonstrated evidence of proficient achievement of course learning outcomes.

Course grade description: To achieve a grade of 5, a student must achieve an overall mark of at least 65% and not meet the requirements for a higher grade.

6 (Distinction) 75 -

Demonstrated evidence of advanced achievement of course learning outcomes.

Course grade description: To achieve a grade of 6, a student must achieve an overall mark of at least 75% and not meet the requirements for a higher grade.

7 (High Distinction) 85 -

Demonstrated evidence of exceptional achievement of course learning outcomes.

Course grade description: To achieve a grade of 7, a student must achieve an overall mark of at least 85%.

Additional course grading information

Your overall mark is the larger of

(1) the sum of your assignment mark out of 10, your in-semester exam mark out of 36 and your end-of-semester exam mark out of 54, and

(2) the sum of your assignment mark out of 10 and your end-of-semester exam mark out of 90.

Supplementary assessment

Supplementary assessment is available for this course.

Should you fail a course with a grade of 3, you may be eligible for supplementary assessment. Refer to my.UQ for information on supplementary assessment and how to apply. 

Supplementary assessment provides an additional opportunity to demonstrate you have achieved all the required learning outcomes for a course.  

If you apply and are granted supplementary assessment, the type of supplementary assessment set will consider which learning outcome(s) have not been met.  

Supplementary assessment in this course will be a 2-hour examination similar in style to the end-of-semester examination. To receive a passing grade of 3S4, you must obtain a mark of 50% or more on the supplementary assessment. 

Additional assessment information

Artificial Intelligence

The assessment tasks in this course evaluate students’ abilities, skills and knowledge without the aid of Artificial Intelligence (AI). Students are advised that the use of AI technologies to develop responses is strictly prohibited and may constitute misconduct under the Student Code of Conduct.

Applications for Extensions to Assessment Due Dates

Extension requests are submitted online via my.UQ – applying for an extension. Extension requests received in any other way will not be approved. Additional details associated with extension requests, including acceptable and unacceptable reasons, may be found at my.UQ.

Please note:

  • Requests for an extension to an assessment due date must be submitted through your my.UQ portal and you must provide documentation of your circumstances, as soon as it becomes evident that an extension is needed. Your application must be submitted on or before the assessment item's due date and time.
  • Applications for extension can take time to be processed so you should continue to work on your assessment item while awaiting a decision. We recommend that you submit any completed work by the due date, and this will be marked if your application is not approved. Should your application be approved, then you will be able to resubmit by the agreed revised due date.
  • If an extension is approved, you will be notified via your my.UQ portal and the new date and time for submission provided. It is important that you check the revised date as it may differ from the date that you requested.
  • If the basis of the application is a medical condition, applications should be accompanied by a medical certificate dated prior to the assignment due date. If you are unable to provide documentation to support your application by the due date and time you must still submit your application on time and attach a written statement (Word document) outlining why you cannot provide the documentation. You must then upload the documentation to the portal within 24 hours.
  • If an extension is being sought on the basis of exceptional circumstances, it must be accompanied by supporting documentation (eg. Statutory declaration).
  • For extensions based on a SAP you may be granted a maximum of 7 days (if no earlier maximum timeframe applies). See the Extension or Deferral availability section of each assessment for details. Your SAP is all that is required as documentation to support your application. However, additional extension requests for the assessment item will require the submission of additional supporting documentation e.g., a medical certificate. All extension requests must be received by the assessment due date and time.
  • An extension for an assessment item due within the teaching period in which the course is offered, must not exceed four weeks in total. If you are incapacitated for a period exceeding four weeks of the teaching period, you are advised to apply for Removal of Course.
  • If you have been ill or unable to attend class for more than 14 days, you are advised to carefully consider whether you are capable of successfully completing your courses this semester. You might be eligible to withdraw without academic penalty - seek advice from the Faculty that administers your program.
  • Students may be asked to submit evidence of work completed to date. Lack of adequate progress on your assessment item may result in an extension being denied.
  • There are no provisions for exemption from an assessment item within UQ rules. If you are unable to submit an assessment piece then, under special circumstances, you may be granted an exemption, but may be required to submit alternative assessment to ensure all learning outcomes are met.

Applications to defer an exam

In certain circumstances you can apply to take a deferred examination for in-semester and end-of-semester exams. You'll need to demonstrate through supporting documentation how unavoidable circumstances prevented you from sitting your exam. If you can’t, you can apply for a one-off discretionary deferred exam.

Deferred Exam requests are submitted online via mySi-net. Requests received in any other way will not be approved. Additional details associated with deferred examinations, including acceptable and unacceptable reasons may be found at my.UQ.

Please note:

  • Applications can be submitted no later than 5 calendar days after the date of the original exam.
  • There are no provisions to defer a deferred exam. You need to be available to sit your deferred examination.
  • Your deferred examination request(s) must have a status of "submitted" in mySI-net to be assessed.
  • All applications for deferred in-semester examinations are assessed by the relevant school. Applications for deferred end-of-semester examinations are assessed by the Academic Services Division.
  • You’ll receive an email to your student email account when the status of your application is updated.
  • If you have a medical condition, mental health condition or disability and require alternative arrangements for your deferred exam you’ll need to complete the online alternative exam arrangements through my.UQ. This is in addition to your deferred examinations request. You need to submit this request on the same day as your request for a deferred exam or supplementary assessment. Contact Student Services if you need assistance completing your alternative exam arrangements request.

Learning resources

You'll need the following resources to successfully complete the course. We've indicated below if you need a personal copy of the reading materials or your own item.

Library resources

Find the required and recommended resources for this course on the UQ Library website.

Additional learning resources information

All required learning resources will be supplied on the Blackboard page.

Learning activities

The learning activities for this course are outlined below. Learn more about the learning outcomes that apply to this course.

Filter activity type by

Please select
Clear filters
Learning period Activity type Topic
Multiple weeks
General contact hours

Weeks 1 to 13

This course has two 2-hour classes per week. These are listed as three lectures and one tutorial in UQ's timetable, but in practice each 2-hour class will be a combination of lecture and tutorial.

Additional learning activity information

This course has two 2-hour classes per week. These are listed as three lectures and one tutorial in UQ's timetable, but in practice each 2-hour class will be a combination of lecture and tutorial.

Policies and procedures

University policies and procedures apply to all aspects of student life. As a UQ student, you must comply with University-wide and program-specific requirements, including the:

Learn more about UQ policies on my.UQ and the Policy and Procedure Library.