CAB301 Algorithms and Complexity
To view more information for this unit, select Unit Outline from the list below. Please note the teaching period for which the Unit Outline is relevant.
| Unit code: | CAB301 |
|---|---|
| Prerequisite(s): | (CAB201 or ITD121) |
| Equivalent(s): | INB371 |
| Credit points: | 12 |
| Timetable | Details in HiQ, if available |
| Availabilities |
|
| CSP student contribution | $1,118 |
| Domestic tuition unit fee | $4,104 |
| International unit fee | $4,788 |
Unit Outline: Semester 1 2024, Gardens Point, Internal
| Unit code: | CAB301 |
|---|---|
| Credit points: | 12 |
| Pre-requisite: | (CAB201 or ITD121) |
| Equivalent: | INB371 |
| Coordinator: | Maolin Tang | m.tang@qut.edu.au |
Overview
This unit teaches you the fundamental principles used to assess the efficiency of software algorithms, allowing you to distinguish solutions that can process large amounts of data or perform complex calculations effectively from those that run unacceptably slowly or not at all. In this unit you will examine a range of different algorithms, review the principles used to predict their efficiency and perform empirical measurements of specific algorithms to confirm the theoretical predictions.
Learning Outcomes
On successful completion of this unit you will be able to:
- Explain the profound importance of efficiency and its effect on the feasibility of a solution
- Analyse the time efficiently of algorithms using both theoretical and empirical means
- Integrate a range of well-known classes of data structures and algorithms to solve real world software problems
- Design novel algorithms for solving complex computational problems.
- Write a technical report that meets industry standards for a specialist audience.
Content
• Computational complexity analysis and theory
• Sorting algorithms
• Searching
• Tree and Graph algorithms
• String processing algorithms
Learning Approaches
This unit is available for you to study in either on-campus or online mode. You can expect to spend 10 hours per week involved in preparing for and attending scheduled classes, preparing and completing assessment tasks as well as independent study and consolidation of your learning.
This unit provides an engaging mix of theory and artefact-driven practice. The principles of algorithm design and performance prediction are presented via a range of examples. This theory is then reinforced through a problem solving task and a paired project which require you to compare theoretical predictions with actual behaviour and to reflect on the reasons for any differences found.
Feedback on Learning and Assessment
You will receive formative feedback in class. Summative and formative feedback will be supplied for the assignments. Summative feedback will be provided via the examination. You will also be required to communicate the results of your technical work in a form easily understood by your peers.
Assessment
Overview
Although founded in theory, this unit emphasises complementary practical skills. In particular, the assignments (problem solving task and project) provide a clear link between theory and practice. You are required to be self-sufficient in implementing computer programs given detailed algorithmic descriptions.
Unit Grading Scheme
7- point scale
Assessment Tasks
Assessment: Assignment 1
This assignment is to assess your knowledge about linear data structures and algorithms and your skills in applying the knowledge in the development of reusable Abstract Data Types (ADTs).
In this assignment, you will be given the specifications of two to three ADT specifications in C# interfaces. Your job is to implement the ADT specifications using specified linear data structures and algorithms. You also need to design efficient algorithms to solve some computational problems arising in the implementation of those operations in the ADT specifications and analyse the time efficiency of the algorithms.
This is an assignment for the purposes of an extension.
Assessment: Assignment 2
This assignment is to assess your knowledge about nonlinear data structures and algorithms and your skills in applying the knowledge in the development of reusable Abstract Data Types (ADTs).
In this assignment, you will be given the specifications of two to three ADT specifications in C# interfaces. Your job is to implement the ADT specifications using specified nonlinear data structures and algorithms. You also need to design efficient algorithms to solve some computational problems arising in the implementation of those operations in the ADT specifications and analyse the time efficiency of the algorithms.
Assessment: Project
This assignment is to assess your knowledge about data structures and algorithms and your skills in applying the knowledge in a real-world software development project.
In this assignment, you may need to use the ADTs that you developed in Assignment 1 and/or Assignment 2, and you may also need to develop some new ADTs and use the ADTs in the software development. In addition, in this assignment you need to design efficient algorithms to solve some computational problems in the software development and empirically analyse the time efficiency of the algorithms that you designed.
This is an assignment for the purposes of an extension.
Academic Integrity
Students are expected to engage in learning and assessment at QUT with honesty, transparency and fairness. Maintaining academic integrity means upholding these principles and demonstrating valuable professional capabilities based on ethical foundations.
Failure to maintain academic integrity can take many forms. It includes cheating in examinations, plagiarism, self-plagiarism, collusion, and submitting an assessment item completed by another person (e.g. contract cheating). It can also include providing your assessment to another entity, such as to a person or website.
You are encouraged to make use of QUT’s learning support services, resources and tools to assure the academic integrity of your assessment. This includes the use of text matching software that may be available to assist with self-assessing your academic integrity as part of the assessment submission process.
Further details of QUT’s approach to academic integrity are outlined in the Academic integrity policy and the Student Code of Conduct. Breaching QUT’s Academic integrity policy is regarded as student misconduct and can lead to the imposition of penalties ranging from a grade reduction to exclusion from QUT.
Resources
Risk Assessment Statement
There are no unusual health or safety risks associated with this unit.
Disclaimer - Offer of some units is subject to viability, and information in these Unit Outlines is subject to change prior to commencement of semester.
Standards/Competencies
This unit is designed to support your development of the following standards\competencies.
Australian Computer Society Core Body of Knowledge
2: ICT Problem Solving
3: Technology Resources
- Data and information management
Relates to: ULO3
Engineers Australia Stage 1 Competency Standard for Professional Engineer
1: Knowledge and Skill Base
Relates to: Project
Relates to: Assignment 1, Assignment 2, Project
2: Engineering Application Ability
Relates to: Assignment 1, Assignment 2, Project
Relates to: Assignment 1, Assignment 2
Relates to: Project
3: Professional and Personal Attributes
Relates to: Assignment 1, Assignment 2
The Global Skills and Competency framework for a digital world
PROG: Programming/Software Development
Course Learning Outcomes
This unit is designed to support your development of the following course/study area learning outcomes.EN01 Bachelor of Engineering (Honours)
- Engage stakeholders professionally and communicate the outcomes of your work effectively to expert and non-expert audiences using appropriate modes.
Relates to: ULO5, Project - Display leadership, creativity, and initiative in both self-directed and collaborative contexts of professional engineering practice.
Relates to: Project - Manage projects to solve complex engineering problems, using appropriate information, engineering methods, and technologies.
Relates to: ULO2, ULO4, Assignment 1, Assignment 2, Project - Deploy appropriate approaches to engineering design and quality.
Relates to: ULO3, Assignment 1, Assignment 2, Project - Demonstrate a thorough understanding of one engineering discipline, its research directions, and its application in contemporary professional engineering practice.
Relates to: ULO1, Assignment 1, Assignment 2
EV01 Bachelor of Engineering (Honours)
- Engage stakeholders professionally and communicate the outcomes of your work effectively to expert and non-expert audiences using appropriate modes.
Relates to: Project - Display leadership, creativity, and initiative in both self-directed and collaborative contexts of professional engineering practice.
Relates to: Project - Manage projects to solve complex engineering problems, using appropriate information, engineering methods, and technologies.
Relates to: Assignment 1, Assignment 2, Project - Deploy appropriate approaches to engineering design and quality.
Relates to: Assignment 1, Assignment 2, Project - Demonstrate a thorough understanding of one engineering discipline, its research directions, and its application in contemporary professional engineering practice.
Relates to: Assignment 1, Assignment 2
IN01 Bachelor of Information Technology
- Demonstrate well-developed IT discipline knowledge
Relates to: ULO1 - Employ appropriate IT Methods
Relates to: ULO2 - Critically apply design and problem solving skills
Relates to: ULO4 - Communicate effectively in professional contexts
Relates to: ULO5 - Create considered and relevant IT solutions
Relates to: ULO3
IN05 Bachelor of Games and Interactive Environments
- Demonstrate broad knowledge of games and interactive environments principles and theory, with an in-depth knowledge of one games-related discipline.
Relates to: ULO1, Assignment 1, Assignment 2 - Apply creativity, critical thinking and problem-solving skills to generate solutions to design challenges.
Relates to: ULO2, ULO3, ULO4, Assignment 1, Assignment 2, Project - Create engaging and meaningful games experiences for specific target audiences in partnership with diverse industry and community stakeholders using industry-relevant software and technologies..
Relates to: ULO3, ULO4, Assignment 1, Assignment 2, Project - Communicate complex concepts at all stages of the development cycle to specialist and non-specialist audiences in written, oral and interactive visual formats.
Relates to: ULO5, Project - Evidence the development of your learning, professional capabilities and skills through creating a curated portfolio of work.
Relates to: ULO4, Project
Unit Outline: Semester 1 2024, Online
| Unit code: | CAB301 |
|---|---|
| Credit points: | 12 |
| Pre-requisite: | (CAB201 or ITD121) |
| Equivalent: | INB371 |
Overview
This unit teaches you the fundamental principles used to assess the efficiency of software algorithms, allowing you to distinguish solutions that can process large amounts of data or perform complex calculations effectively from those that run unacceptably slowly or not at all. In this unit you will examine a range of different algorithms, review the principles used to predict their efficiency and perform empirical measurements of specific algorithms to confirm the theoretical predictions.
Learning Outcomes
On successful completion of this unit you will be able to:
- Explain the profound importance of efficiency and its effect on the feasibility of a solution
- Analyse the time efficiently of algorithms using both theoretical and empirical means
- Integrate a range of well-known classes of data structures and algorithms to solve real world software problems
- Design novel algorithms for solving complex computational problems.
- Write a technical report that meets industry standards for a specialist audience.
Content
• Computational complexity analysis and theory
• Sorting algorithms
• Searching
• Tree and Graph algorithms
• String processing algorithms
Learning Approaches
This unit is available for you to study in either on-campus or online mode. You can expect to spend 10 hours per week involved in preparing for and attending scheduled classes, preparing and completing assessment tasks as well as independent study and consolidation of your learning.
This unit provides an engaging mix of theory and artefact-driven practice. The principles of algorithm design and performance prediction are presented via a range of examples. This theory is then reinforced through a problem solving task and a paired project which require you to compare theoretical predictions with actual behaviour and to reflect on the reasons for any differences found.
Feedback on Learning and Assessment
You will receive formative feedback in class. Summative and formative feedback will be supplied for the assignments. Summative feedback will be provided via the examination. You will also be required to communicate the results of your technical work in a form easily understood by your peers.
Assessment
Overview
Although founded in theory, this unit emphasises complementary practical skills. In particular, the assignments (problem solving task and project) provide a clear link between theory and practice. You are required to be self-sufficient in implementing computer programs given detailed algorithmic descriptions.
Unit Grading Scheme
7- point scale
Assessment Tasks
Assessment: Assignment 1
This assignment is to assess your knowledge about linear data structures and algorithms and your skills in applying the knowledge in the development of reusable Abstract Data Types (ADTs).
In this assignment, you will be given the specifications of two to three ADT specifications in C# interfaces. Your job is to implement the ADT specifications using specified linear data structures and algorithms. You also need to design efficient algorithms to solve some computational problems arising in the implementation of those operations in the ADT specifications and analyse the time efficiency of the algorithms.
This is an assignment for the purposes of an extension.
Assessment: Assignment 2
This assignment is to assess your knowledge about nonlinear data structures and algorithms and your skills in applying the knowledge in the development of reusable Abstract Data Types (ADTs).
In this assignment, you will be given the specifications of two to three ADT specifications in C# interfaces. Your job is to implement the ADT specifications using specified nonlinear data structures and algorithms. You also need to design efficient algorithms to solve some computational problems arising in the implementation of those operations in the ADT specifications and analyse the time efficiency of the algorithms.
Assessment: Project
This assignment is to assess your knowledge about data structures and algorithms and your skills in applying the knowledge in a real-world software development project.
In this assignment, you may need to use the ADTs that you developed in Assignment 1 and/or Assignment 2, and you may also need to develop some new ADTs and use the ADTs in the software development. In addition, in this assignment you need to design efficient algorithms to solve some computational problems in the software development and empirically analyse the time efficiency of the algorithms that you designed.
This is an assignment for the purposes of an extension.
Academic Integrity
Students are expected to engage in learning and assessment at QUT with honesty, transparency and fairness. Maintaining academic integrity means upholding these principles and demonstrating valuable professional capabilities based on ethical foundations.
Failure to maintain academic integrity can take many forms. It includes cheating in examinations, plagiarism, self-plagiarism, collusion, and submitting an assessment item completed by another person (e.g. contract cheating). It can also include providing your assessment to another entity, such as to a person or website.
You are encouraged to make use of QUT’s learning support services, resources and tools to assure the academic integrity of your assessment. This includes the use of text matching software that may be available to assist with self-assessing your academic integrity as part of the assessment submission process.
Further details of QUT’s approach to academic integrity are outlined in the Academic integrity policy and the Student Code of Conduct. Breaching QUT’s Academic integrity policy is regarded as student misconduct and can lead to the imposition of penalties ranging from a grade reduction to exclusion from QUT.
Resources
Risk Assessment Statement
There are no unusual health or safety risks associated with this unit.
Disclaimer - Offer of some units is subject to viability, and information in these Unit Outlines is subject to change prior to commencement of semester.
Standards/Competencies
This unit is designed to support your development of the following standards\competencies.
Australian Computer Society Core Body of Knowledge
2: ICT Problem Solving
3: Technology Resources
- Data and information management
Relates to: ULO3
Engineers Australia Stage 1 Competency Standard for Professional Engineer
1: Knowledge and Skill Base
Relates to: Project
Relates to: Assignment 1, Assignment 2, Project
2: Engineering Application Ability
Relates to: Assignment 1, Assignment 2, Project
Relates to: Assignment 1, Assignment 2
Relates to: Project
3: Professional and Personal Attributes
Relates to: Assignment 1, Assignment 2
The Global Skills and Competency framework for a digital world
PROG: Programming/Software Development
Course Learning Outcomes
This unit is designed to support your development of the following course/study area learning outcomes.EN01 Bachelor of Engineering (Honours)
- Engage stakeholders professionally and communicate the outcomes of your work effectively to expert and non-expert audiences using appropriate modes.
Relates to: ULO5, Project - Display leadership, creativity, and initiative in both self-directed and collaborative contexts of professional engineering practice.
Relates to: Project - Manage projects to solve complex engineering problems, using appropriate information, engineering methods, and technologies.
Relates to: ULO2, ULO4, Assignment 1, Assignment 2, Project - Deploy appropriate approaches to engineering design and quality.
Relates to: ULO3, Assignment 1, Assignment 2, Project - Demonstrate a thorough understanding of one engineering discipline, its research directions, and its application in contemporary professional engineering practice.
Relates to: ULO1, Assignment 1, Assignment 2
EV01 Bachelor of Engineering (Honours)
- Engage stakeholders professionally and communicate the outcomes of your work effectively to expert and non-expert audiences using appropriate modes.
Relates to: Project - Display leadership, creativity, and initiative in both self-directed and collaborative contexts of professional engineering practice.
Relates to: Project - Manage projects to solve complex engineering problems, using appropriate information, engineering methods, and technologies.
Relates to: Assignment 1, Assignment 2, Project - Deploy appropriate approaches to engineering design and quality.
Relates to: Assignment 1, Assignment 2, Project - Demonstrate a thorough understanding of one engineering discipline, its research directions, and its application in contemporary professional engineering practice.
Relates to: Assignment 1, Assignment 2
IN01 Bachelor of Information Technology
- Demonstrate well-developed IT discipline knowledge
Relates to: ULO1 - Employ appropriate IT Methods
Relates to: ULO2 - Critically apply design and problem solving skills
Relates to: ULO4 - Communicate effectively in professional contexts
Relates to: ULO5 - Create considered and relevant IT solutions
Relates to: ULO3
IN05 Bachelor of Games and Interactive Environments
- Demonstrate broad knowledge of games and interactive environments principles and theory, with an in-depth knowledge of one games-related discipline.
Relates to: ULO1, Assignment 1, Assignment 2 - Apply creativity, critical thinking and problem-solving skills to generate solutions to design challenges.
Relates to: ULO2, ULO3, ULO4, Assignment 1, Assignment 2, Project - Create engaging and meaningful games experiences for specific target audiences in partnership with diverse industry and community stakeholders using industry-relevant software and technologies..
Relates to: ULO3, ULO4, Assignment 1, Assignment 2, Project - Communicate complex concepts at all stages of the development cycle to specialist and non-specialist audiences in written, oral and interactive visual formats.
Relates to: ULO5, Project - Evidence the development of your learning, professional capabilities and skills through creating a curated portfolio of work.
Relates to: ULO4, Project