Note: This unit version is currently being edited and is subject to change!

COMP2823: Data Structures & Algorithms (Adv) (2019 - Semester 1)

Download UoS Outline

Unit: COMP2823: Data Structures & Algorithms (Adv) (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Intermediate
Faculty/School: School of Computer Science
Unit Coordinator/s: Dr Mestre, Julian
Session options: Semester 1
Versions for this Unit:
Site(s) for this Unit: http://elearning.sydney.edu.au
Campus: Camperdown/Darlington
Pre-Requisites: INFO1110 OR INFO1910 OR INFO1113 OR DATA1002 OR DATA1902 OR INFO1103 OR INFO1903. Distinction-level result in at least one the above 1000 level programming units
Prohibitions: INFO1105 OR INFO1905 OR COMP2123.
Brief Handbook Description: This unit will teach some powerful ideas that are central to solving algorithmic problems in ways that are more efficient than naïve approaches. In particular, students will learn how data collections can support efficient access, for example, how a dictionary or map can allow key-based lookup that does not slow down linearly as the collection grows in size. The data structures covered in this unit include lists, stacks, queues, priority queues, search trees, hash tables, and graphs. Students will also learn efficient techniques for classic tasks such as sorting a collection. The concept of asymptotic notation will be introduced, and used to describe the costs of various data access operations and algorithms.
Assumed Knowledge: None.
Lecturer/s: Dr Mestre, Julian
Timetable: COMP2823 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 3.00 1 13
2 Tutorial 3.00 1 12
3 Independent Study 6.00 13

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.

(6) Communication and Inquiry/ Research (Level 2)
1. Proficiency in organising, presenting and discussing professional ideas and issues in oral, written and graphic formats. Thorough descriptive reporting. With thorough consideration of format and audience requirements. Fluent presentation of engineering/IT concepts and issues to professional and non-professional audiences, using a varied range of professional communication tools and formats.
(4) Design (Level 2)
2. Experience designing an algorithmic solution to a problem, coding it, and analysing its complexity.
(3) Problem Solving and Inventiveness (Level 2)
3. Ability to write code that recursively performs an operation on a data structure.
4. Ability to apply basic algorithmic techniques (e.g. divide-and-conquer, greedy) to given design tasks.
(2) Engineering/ IT Specialisation (Level 2)
5. Using notation of big-Oh to represent asymptotic growth of cost functions
6. Understanding of commonly used (and some more sophisticated) 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.
7. Understanding of basic (and some more sophisticated) algorithms related to data structures, such as algorithms for sorting, tree traversals, and graph traversals.
(1) Maths/ Science Methods and Tools (Level 2)
8. Using mathematical methods to evaluate the performance of an algorithm.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Assignments No 30.00 Multiple Weeks (Tuesday) 1, 2, 3, 4, 5, 6, 7, 8,
2 Quizzes No 20.00 Multiple Weeks 4, 5, 6, 7, 8,
3 Final exam No 50.00 Exam Period 1, 3, 4, 5, 6, 7, 8,
Assessment Description: Assignments: Short weekly assignments alternating between paper based and programming. Each assignment is worth 3 points.

Quizzes: Short weekly multiple-choice quizzes, during tutorial times, on e-learning. Each quiz is worth 2 points.

Final Exam: Final Written Examination.
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.
Minimum Pass Requirement It is a policy of the School of Computer Science that in order to pass this unit, a student must achieve at least 40% in the written examination. For subjects without a final exam, the 40% minimum requirement applies to the corresponding major assessment component specified by the lecturer. A student must also achieve an overall final mark of 50 or more. Any student not meeting these requirements may be given a maximum final mark of no more than 45 regardless of their average.
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of Computer Science 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.
Recommended Reference/s: Note: References are provided for guidance purposes only. Students are advised to consult these books in the university library. Purchase is not required.
  • Algorithm Design and Aopplications
Online Course Content: Sydney elearning site: http://elearning.sydney.edu.au
Note on Resources: Students may prefer to mainly use one of the language-specific books by the smae authors: Data Structures & Algorithms in Java (6th ed) or Data Structures & Algorithms in Python

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 Administrivia
Definitions and precision regarding scalability and analysis of algorithms
Algorithm analysis, review of Python and Java
Week 2 Stacks and Queues
Abstract Data Structures
Week 3 Tree concepts and definitions
Recursion on a tree
Binary tree implementation, general tree implementation
Week 4 Binary tree implementation, general tree implementation; recursion on a tree
Balanced binary search tree (AVL tree)
Week 5 Simple map implementation by list (sorted and unsorted)
Priority queues; heap-as-a-tree and heap-in-array; sorting using priority queue
Week 6 Hashing
Week 7 Graph representations
Graph traversals
Week 8 Shortest path algorithm
Minimum weight spanning tree algorithms
Week 9 Greedy Method
Week 10 Divide-and-conquer
Week 11 Divide-and-conquer
Week 12 Randomized algorithms
Week 13 Review of Unit of Study and exam preparation
Exam Period 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
Biomedical Mid-Year 2016, 2017, 2018, 2019, 2020
Biomedical 2016, 2017, 2018, 2019, 2020
Bachelor of Computer Science and Technology (Advanced) 2017

Course Goals

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

Attribute Practiced Assessed
(5) Interdisciplinary, Inclusiveness, Influence (Level 2) No 0%
(6) Communication and Inquiry/ Research (Level 2) No 8%
(4) Design (Level 2) No 4.5%
(3) Problem Solving and Inventiveness (Level 2) No 24.5%
(2) Engineering/ IT Specialisation (Level 2) No 51%
(1) Maths/ Science Methods and Tools (Level 2) No 12%

These goals are selected from Engineering & IT Graduate Outcomes Table 2018 which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 2018 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.