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

UTS: Information Technology: Software
Credit points: 6 cp

Subject level:

Undergraduate

Result type: Grade and marks

Requisite(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)

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.

Course intended learning outcomes (CILOs)

This subject also contributes specifically to the development of the following Course Intended Learning Outcomes (CILOs):

• Identify and apply relevant problem solving methodologies (B.1)
• Design components, systems and/or processes to meet required specifications (B.2)
• Implement and test solutions (B.5)

Content (topics)

1. C++ constructs including templates and the STL
2. Program design
3. Design, implementation, and evaluation of data structures
4. Design, implementation, and evaluation of algorithms
5. Recursion
6. Computability, NP-Completeness, Optimization

Assessment

Assessment task 1: Programming Assignment 1

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): B.1, B.2 and B.5
Type:	Exercises
Groupwork:	Individual
Weight:	25%
Length:	200-300 lines of code.
Criteria linkages:	Criteria Weight (%) SLOs CILOs Functionality 50 2, 3, 4, 5 B.5 Design 35 2, 3, 4, 5 B.2 Programming Style 15 2, 3, 4, 5 B.1 SLOs: subject learning objectives CILOs: course intended learning outcomes

Assessment task 2: Programming Assignment 2

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): B.1, B.2 and B.5
Type:	Exercises
Groupwork:	Individual
Weight:	35%
Length:	300-400 lines of code.
Criteria linkages:	Criteria Weight (%) SLOs CILOs Functionality 50 2, 3, 4, 5 B.5 Design 35 2, 3, 4, 5 B.2 Programming Style 15 2, 3, 4, 5 B.1 SLOs: subject learning objectives CILOs: course intended learning outcomes

Assessment task 3: Final Examination

Objective(s):	This assessment task addresses the following subject learning objectives (SLOs): 1 This assessment task contributes to the development of the following course intended learning outcomes (CILOs): B.1
Type:	Examination
Groupwork:	Individual
Weight:	40%
Length:	2 Hour exam
Criteria linkages:	Criteria Weight (%) SLOs CILOs Correctness of solution in 25 multiple choice questions 100 1 B.1 SLOs: subject learning objectives CILOs: course intended learning outcomes

Minimum requirements

In order to pass the subject you must attain all of the following minimum requirements

1. Minimum of 16 out of 40 (40%) in the final exam.
2. Minimum of 50 out of 100 (50%) in the overall mark

If you fail to achieve the first requirement but meet the second then your final grade will be set to X (fail)

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

S. Lippman, J. Lagoie & B. Moo
C++ Primer - 4th Edition.
Probably the main reference book around on C++. Most C++ programmers would have a copy of this on their bookshelf

N. Josuttis
The C++ Standard Library: A Tutorial and Reference
A very useful book that goes into the details of the STL.

Online References
http://www.cppreference.com/
http://www.cplusplus.com/

Other resources

Computer account
You will need to have a student computer account with the Faculty of Engineering and Information Technology. If you are a faculty student you will already have one. If you are a non-faculty student you will need to ensure you have one. If you are unsure, or need to arrange an account, then you can contact the FEIT Technical Support Help Desk.

SUBNET
Material related to the course will be made available on the SUBNET site.
https://learn.it.uts.edu.au/netapp/Subjects/DSA/index.php

Additionally, any further information about the subject will be announced on the SUBNET site. You should check SUBNET regularly for any updates.

UTS Online
This subject makes use of UTS Online, particularly the discussions boards. Students are strongly encouraged to make use of the discussion boards to ask questions to help with their learning. You should check UTS Online regularly.