Note: This unit is an archived version! See Overview tab for delivered versions.
INFO1905: Data Structures (Advanced) (2017 - Semester 2)
| Unit: | INFO1905: Data Structures (Advanced) (6 CP) |
| Mode: | Normal-Day |
| On Offer: | Yes |
| Level: | Junior |
| Faculty/School: | School of Computer Science |
| Unit Coordinator/s: |
Prof Fekete, Alan
|
| Session options: | Semester 2 |
| Versions for this Unit: | |
| Site(s) for this Unit: |
| Campus: | Camperdown/Darlington |
| Pre-Requisites: | INFO1103 OR INFO1903. Distinction-level performance in INFO1103 or INFO1903 |
| Prohibitions: | INFO1105. |
| 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: | To enter this unit, students need to possess programming knowledge skills at the level of INFO1103 or INFO1903. Expected knowledge includes use of the Java collections APIs and recursion. Chapters 1, 2, 3 and 9 of the textbook provide review material on these topics. Students who have passed similar units at other universities should apply for special permission to enrol. |
| Lecturer/s: |
Professor Hong, SeokHee
Prof Fekete, Alan |
||||||||||||||||||||
| Timetable: | INFO1905 Timetable | ||||||||||||||||||||
| Time Commitment: |
|
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)| Assessment Methods: |
|
||||||||||||||||||||||||||||||||||||||||||||||||
| Assessment Description: |
Quiz: Multiple quizzes during tutorial times throughout the semester. Each quiz may be computer-based or paper-based. In case of special consideration, extensions or alternative sittings will not be offered; instead, reweighting should be applied. Tasks: Mulriple programming exercises throughout the semester, automatically graded. Assignments: Practical individual work that may include the design, implementation and analysis of data structures. AsstX and AsstY deal with the additional advanced material. Final Exam: Covering all aspects of the unit of study. |
||||||||||||||||||||||||||||||||||||||||||||||||
| Grading: |
|
||||||||||||||||||||||||||||||||||||||||||||||||
| 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. |
| 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.
|
| Online Course Content: | Sydney elearning site |
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 | Introduction, Administrivia, Data Abstraction, Map and List |
| Week 2 | Linked Lists; Iterators |
| Week 3 | Stacks and queues; Describing scalability, analysis of scalability. |
| Week 4 | Trees: definitions, traversals, implementation, recursive code |
| Week 5 | Heaps and priority queues; sorting using Priority Queue |
| Week 6 | Binary search trees |
| Assessment Due: AsstX | |
| Week 7 | Hashing; Sets |
| Week 8 | Reasoning about scalability |
| Assessment Due: Assignment 1 | |
| Week 9 | Graphs |
| Week 10 | Graphs |
| Week 11 | More sorting algorithms |
| Assessment Due: AsstY | |
| Week 12 | Spare for catch-up, revision or in-class practice exercise |
| Assessment Due: Assignment 2 | |
| Week 13 | Unit of Study Review 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 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 | 12.95% |
| Engineering/IT Specialisation (Level 2) | Yes | 87.05% |
| 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.
