31251 Data Structures and Algorithms
Warning: The information on this page is indicative. The subject outline for a
particular session, location and mode of offering is the authoritative source
of all information about the subject for that offering. Required texts, recommended texts and references in particular are likely to change. Students will be provided with a subject outline once they enrol in the subject.
Subject handbook information prior to 2022 is available in the Archives.
Credit points: 6 cp
Subject level:
Undergraduate
Result type: Grade and marksRequisite(s): 48024 Applications Programming
Anti-requisite(s): 31473 Data Structures and Procedural Programming AND 32510 Principles of Object-oriented Programming in C++
Recommended studies:
basic programming concepts: variables, loops and decisions; basic file manipulation in UNIX: directories and files, editing files, re-direction; basic understanding of the standard Von Neumann computer model: the fetch-execute cycle, single memory with byte addressing, input and output with disks, keyboard and screen; understanding of character sets and internal data representations, including ASCII, signed integers, floating point
Description
This subject teaches students how to design, develop and evaluate data structures and algorithms to meet predefined quality characteristics of functionality (suitability) and usability (understandability, learnability, operability, compliance). Software solutions are implemented using C++. Concepts, theories and technologies underlying the methods and techniques are introduced and explained as required.
Subject learning objectives (SLOs)
Upon successful completion of this subject students should be able to:
| 1. | Explain the basic data structures and algorithms for manipulating them. |
|---|---|
| 2. | Implement these data structures and algorithms in the C++ language. |
| 3. | Integrate these data structures and algorithms in larger programs. |
| 4. | Code and test well-structured programs of moderate size using the C++ language. |
| 5. | Apply principles of good program design to the C++ language. |
| 6. | Demonstrate advanced programming skills. |
Course intended learning outcomes (CILOs)
This subject also contributes specifically to the development of the following Course Intended Learning Outcomes (CILOs):
- Design Oriented: FEIT graduates apply problem solving, design and decision-making methodologies to develop components, systems and processes to meet specified requirements. (C.1)
- Technically Proficient: FEIT graduates apply abstraction, mathematics and discipline fundamentals, software, tools and techniques to evaluate, implement and operate systems. (D.1)
Contribution to the development of graduate attributes
Engineers Australia Stage 1 Competencies
This subject contributes to the development of the following Engineers Australia Stage 1 Competencies:
- 1.2. Conceptual understanding of the mathematics, numerical analysis, statistics, and computer and information sciences which underpin the engineering discipline.
- 2.1. Application of established engineering methods to complex engineering problem solving.
Teaching and learning strategies
Lecture topics and supporting material will be available online, along with readings to be completed before the tutorial. The lectures provide the fundamental background material and guidance to support the students' learning as they implement, evaluate, compare and critique the data structures and algorithms presented throughout the course.
The tutorials provide a point for feedback and to collaboratively experiment with implementations. In tutorial discussion about the material will provide the students a forum to reflect on their learning and consider the input of both their peers and their tutor.
The knowledge that the students build each week around specific data structures and algorithms leads into and supports the completion of their assessment tasks throughout the session.
Feedback for assessments will be given within two weeks of the in class demonstration (for programming assignments) and from completion (for quizzes).
Content (topics)
- C++ constructs including templates and the STL
- Program design
- Design, implementation, and evaluation of data structures
- Design, implementation, and evaluation of algorithms
- Recursion
- Computability, NP-Completeness, Optimization
Assessment
Assessment task 1: Programming Assignment 1
| Intent: | This assessment task allows you to demonstrate an understanding of some of the data structures and algorithms covered in the course to this point, and their implementation in C++. It supports demonstration of the ability to combine individual data structures and algorithms to form a coherent solution to a computational problem. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 2, 3, 4 and 5 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Exercises |
| Groupwork: | Individual |
| Weight: | 25% |
| Length: | 200-300 lines of code. |
Assessment task 2: Programming Assignment 2
| Intent: | This assessment task builds on the skills and knowledge you have developed through the subject and combines more complicated data structures and algorithms in a more sophisticated manner, allowing you to demonstrate ability in advanced programming and a higher level understanding of the main topics areas of the subject. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 2, 3, 4, 5 and 6 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Exercises |
| Groupwork: | Individual |
| Weight: | 35% |
| Length: | 300-400 lines of code. |
Assessment task 3: Final Examination
| Intent: | The final exam assesses your grasp of the discipline knowledge component of the subject. It also allows you to demonstrate your ability to communicate algorithm and data structure design ideas in short form. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1 and 5 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Examination |
| Groupwork: | Individual |
| Weight: | 30% |
| Length: | 2 Hour exam |
Assessment task 4: Quizzes
| Intent: | The quizzes aim to provide regular feedback and basic assessment of your progress through the course by addressing key knowledge points. In conjunction with the weekly programming tasks and communication with your tutor and peers, these help form the primary routine feedback channel for the subject. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1 and 5 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Quiz/test |
| Groupwork: | Individual |
| Weight: | 10% |
Minimum requirements
In order to pass the subject, a student must achieve an overall mark of 50% or more.
Recommended texts
Elliot B. Koffman & Paul A.T. Wolfgang
Objects, Abstraction, Data Structures and Design Using C++
John Wiley & Sons, Inc
ISBN 0-471-46755-3
References
Possibly Useful Books
S. Lippman, J. Lagoie & B. Moo
C++ Primer - 4th Edition.
N. Josuttis
The C++ Standard Library: A Tutorial and Reference
A very useful book that goes into the details of the STL.
D. S. Malik
C++ Programming: Program Design Including Data Structures
A more extensive equivalent of the recommended text.
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein
Introduction to Algorithms
A classic reference text that goes well beyond this subject, but is useful to anyone who plans on being a programmer.
S. Skiena
The Algorithm Design Manual
A really useful algorithms book that includes numerous real-world considerations and anecdotes.
J. Erickson
Algorithms
An excellent, thorough text, licensed under a CCA 4.0 license, so you can get it and print it for free: http://jeffe.cs.illinois.edu/teaching/algorithms/
Online References
References for C++ itself:
http://www.cppreference.com/
http://www.cplusplus.com/
The Unit Testing Suite Used in the Course:
http://cxxtest.com/
Other resources
Canvas
This subject uses Canvas and Ed for announcements, distribution of course materials, assessment submission, and discussion boards. Students are strongly encouraged to make use of the discussion boards to ask questions to help with their learning. Students should check these websites regularly.