University of Technology Sydney

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 2024 is available in the Archives.

UTS: Information Technology: Computer Science
Credit points: 6 cp

Subject level:

Undergraduate

Result type: Grade and marks

Requisite(s): 48024 Programming 2
Anti-requisite(s): 31473 Data Structures and Procedural Programming AND 32510 Principles of Object-oriented Programming in C++

Recommended studies:

Prior programming experience in some language, including understanding of basic programming concepts such as variables, conditional statements, and control flow.

Description

This subject teaches students how to design, evaluate and implement 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 basic algorithms and the data structures they use. (D.1)
2. Implement basic data structures and algorithms in the C++ language. (D.1)
3. Apply data structures and algorithms in larger programs. (D.1)
4. Code and test well-structured programs of moderate size using the C++ language. (D.1)
5. Apply principles of good program design to the C++ language. (C.1)
6. Demonstrate advanced programming skills. (D.1)

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)

  1. C++ constructs including templates and the standard library
  2. Program design
  3. Design, implementation, and evaluation of data structures
  4. Design, implementation, and evaluation of algorithms
  5. Recursion

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++. Students will gain a greater understanding of how data structures in the C++ standard library are implemented, and explore how algorithmic decisions affect the performance of a program.

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: 20%
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: 30%
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:

Students are given 24 hours to complete the exam.

Assessment task 4: Weekly theoretical and practical exercises

Intent:

Every week there will be short multiple choice quiz and a programming exercise.

The quiz aims to provide regular feedback and basic assessment of your progress through the course by addressing key knowledge points. Programming is a skill that requires consistent practice which is provided by the weekly programming exercise. This allows you to interact with the material from lecture by coding it yourself, and to engage in algorithmic problem solving. This assessment forms the primary routine feedback channel for the subject.

Objective(s):

This assessment task addresses the following subject learning objectives (SLOs):

1, 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: Quiz/test
Groupwork: Individual
Weight: 20%

Minimum requirements

In order to pass the subject, a student must achieve an overall mark of 50% or more.

References

Bjarne Stroustrup
The C++ Programming Language, 4th Edition
Addison-Wesley

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein
Introduction to Algorithms
MIT Press

J. Erickson
Algorithms
An excellent, thorough text, licensed under a CCA 4.0 license, so you can get it for free:

http://jeffe.cs.illinois.edu/teaching/algorithms/

Online Resources

References for C++ itself:

https://en.cppreference.com/w/

https://learncpp.com

?Practice Programming Algorithms and Data Structures:

https://leetcode.com


The unit testing suite used in the course is Google Test:

http://github.com/google/googletest

Other resources

Canvas and Ed
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.