Note: This unit is an archived version! See Overview tab for delivered versions.

INFO1105: Data Structures (2017 - Summer Early)

Download UoS Outline

Unit: INFO1105: Data Structures (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Junior
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr Stavrakakis, John
Session options: Semester 2, Summer Early
Versions for this Unit:
Site(s) for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: INFO1103 OR INFO1903.
Prohibitions: INFO1905.
Brief Handbook Description: The unit will teach some powerful ideas that are central to quality software: data abstraction and recursion. It will also show how one can analyse the scalability of algorithms using mathematical tools of asymptotic notation. Contents include: both external "interface" view, and internal "implementation" details, for commonly used data structures, including lists, stacks, queues, priority queues, search trees, hash tables, and graphs; asymptotic analysis of algorithm scalability, including use of recurrence relations to analyse recursive code. This unit covers the way information is represented in each structure, algorithms for manipulating the structure, and analysis of asymptotic complexity of the operations. Outcomes include: ability to write code that recursively performs an operation on a data structure; experience designing an algorithmic solution to a problem using appropriate data structures, coding the solution, and analysing its complexity.
Assumed Knowledge: None.
Lecturer/s: Dr Stavrakakis, John
Timetable: INFO1105 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 2.00 2 5
2 Laboratory 2.00 3 5
3 Independent Study 8.00 5

Attributes listed here represent the key course goals (see Course Map tab) designated for this unit. The list below describes how these attributes are developed through practice in the unit. See Learning Outcomes and Assessment tabs for details of how these attributes are assessed.

Attribute Development Method Attribute Developed
Transfering problem statments into design, utilizing popular data structures and algorithms to solve problems. Design (Level 2)
Fundamental generic IT/computer science skills: the ability to analyse and manipulate data structures and the ability to design algorithms for this purpose. Engineering/IT Specialisation (Level 2)

For explanation of attributes and levels see Engineering & IT Graduate Outcomes Table.

Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.

Design (Level 2)
1. Ability to analyse scalability of algorithms using mathematical tools of asymptotic notation. They will be able to analyse recursive structures by setting up and solving asymptotic recurrence relations.
Engineering/IT Specialisation (Level 2)
2. Understanding of commonly used data structures, including lists, stacks, queues, priority queues, search trees, hash tables, and graphs. This covers the way information is represented in each structure, algorithms for manipulating the structure, and analysis of asymptotic complexity of the operations.
3. Ability to write code that recursively performs an operation on a data structure.
4. Understanding of basic algorithms related to data structures, such as algorithms for sorting, tree traversals, and graph traversals.
5. Experience designing an algorithmic solution to a problem, coding it, and analysing its complexity.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Tutorial participation No 10.00 Multiple Weeks (Monday, 9 am) 1, 2, 3, 4, 5,
2 Assignment 1 No 10.00 Week 3 (Wednesday, 9 am) 1, 2, 3, 4, 5,
3 Assignment 2 No 10.00 Week 5 (Wednesday, 9 am) 1, 2, 3, 4, 5,
4 Quiz No 20.00 Multiple Weeks 1, 2, 3, 4, 5,
5 Final Exam No 50.00 Week 6 (Tuesday) 1, 2, 3, 4, 5,
Assessment Description: Quiz: Multiple quizzes during tutorial times throughout the course. Each quiz will be computer-based or paper-based.

Assignments: Practical individual work that may include the design, implementation and analysis of data structures.

Tutorial participation: attendance, contribution to tutorial discussion and performance in online activities

Final Exam: Covering all aspects of the unit of study
Grading:
Grade Type Description
Standards Based Assessment Final grades in this unit are awarded at levels of HD for High Distinction, DI (previously D) for Distinction, CR for Credit, PS (previously P) for Pass and FA (previously F) for Fail as defined by University of Sydney Assessment Policy. Details of the Assessment Policy are available on the Policies website at http://sydney.edu.au/policies . Standards for grades in individual assessment tasks and the summative method for obtaining a final mark in the unit will be set out in a marking guide supplied by the unit coordinator.
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of IT may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so.

Other policies

See the policies page of the faculty website at http://sydney.edu.au/engineering/student-policies/ for information regarding university policies and local provisions and procedures within the Faculty of Engineering and Information Technologies.
Prescribed Text/s: Note: Students are expected to have a personal copy of all books listed.
Online Course Content: Sydney elearning site: elearning.sydney.edu.au

Ed: edstem.com.au

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 1 Recursion, Lists
Introduction + Data Abstraction
Analysis tools
Linked lists, stacks queues
Trees
Week 2 Tree traversals, Binary Tree
Priority queues, Heaps
Week 3 Searching and sorting
Hashing
Assessment Due: Assignment 1
Week 4 Graphs
Balanced trees
Week 5 Review
Assessment Due: Assignment 2
Week 6 Assessment Due: Final Exam

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Bachelor of Computer Science and Technology 2015, 2016, 2017, 2025
Computer Engineering / Commerce 2010
Electrical Engineering / Arts 2011, 2012, 2013, 2014
Electrical Engineering / Commerce 2010, 2011, 2012, 2013, 2014
Electrical Engineering (Bioelectronics) / Arts 2011, 2012
Electrical Engineering (Bioelectronics) / Commerce 2011, 2012
Electrical Engineering (Bioelectronics) / Medical Science 2011, 2012
Electrical Engineering (Bioelectronics) / Science 2011, 2012
Electrical Engineering (Bioelectronics) / Law 2011, 2012
Electrical Engineering / Medical Science 2011, 2012, 2013, 2014
Electrical Engineering / Science 2011, 2012, 2013, 2014
Electrical Engineering (Computer) / Arts 2011, 2012, 2013, 2014
Electrical Engineering (Computer) / Commerce 2011, 2012, 2013, 2014
Electrical Engineering (Computer) / Medical Science 2011, 2013, 2014
Electrical Engineering (Computer) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Computer) / Law 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Arts 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Commerce 2010, 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Medical Science 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Power) / Law 2010, 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Arts 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Commerce 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Medical Science 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Science 2011, 2012, 2013, 2014
Electrical Engineering (Telecommunications) / Law 2011, 2012, 2013, 2014
Electrical Engineering 2015, 2016, 2017
Electrical / Arts (2022 and earlier) 2015, 2016, 2017
Electrical / Commerce 2015, 2016, 2017
Electrical / Project Management 2015, 2016, 2017
Electrical / Science 2015, 2016, 2017
Electrical / Law 2015, 2016, 2017
Electrical Engineering (mid-year) 2016, 2017
Software Engineering (mid-year) 2016, 2017
Software Engineering 2015, 2016, 2017
Software / Arts (2022 and earlier) 2015, 2016, 2017
Software / Commerce 2015, 2016, 2017
Software / Project Management 2015, 2016, 2017
Software / Science 2015, 2016, 2017
Software / Law 2015, 2016, 2017
Software Engineering / Arts 2011, 2012, 2013, 2014
Software Engineering / Commerce 2010, 2011, 2012, 2013, 2014
Software Engineering / Medical Science 2011, 2012, 2013, 2014
Software Engineering / Science 2011, 2012, 2013, 2014
Software Engineering / Law 2010, 2011, 2012, 2013, 2014
Flexible First Year (Stream B) / Medical Science 2012, 2013
Aeronautical Engineering / Science 2011, 2012, 2013, 2014
Aeronautical Engineering (Space) / Science 2011, 2012, 2013, 2014
Biomedical Engineering / Science 2013, 2014
Chemical & Biomolecular Engineering / Science 2011, 2012, 2013, 2014
Civil Engineering / Science 2011, 2012, 2013, 2014
Aeronautical / Science 2015, 2016, 2017
Aeronautical (Space) / Science 2015
Biomedical /Science 2015, 2016, 2017
Chemical & Biomolecular / Science 2015
Civil / Science 2015
Mechanical / Science 2015, 2016, 2017
Mechanical (Space) / Science 2015
Mechatronic / Science 2015, 2016, 2017
Mechatronic (Space) / Science 2015
Mechanical Engineering (Biomedical) / Science 2011, 2012
Mechanical Engineering / Science 2011, 2012, 2013, 2014
Mechanical Engineering (Space) / Science 2011, 2012, 2013, 2014
Mechatronic Engineering / Science 2011, 2012, 2013, 2014
Mechatronic Engineering (Space) / Science 2011, 2012, 2013, 2014
Project Engineering and Management (Civil) / Science 2011
Flexible First Year (Stream A) / Science 2012, 2013, 2014
Flexible First Year (Stream B) / Science 2012

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
Maths/Science Methods and Tools (Level 2) No 0%
Project and Team Skills (Level 2) No 0%
Design (Level 2) Yes 13%
Engineering/IT Specialisation (Level 2) Yes 87%
Information Seeking (Level 1) No 0%
Communication (Level 2) No 0%
Professional Conduct (Level 2) No 0%

These goals are selected from Engineering & IT Graduate Outcomes Table which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.