UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
The University of Queensland
School of Information Technology and Electrical Engineering
Semester 2, 2004
COMP2502 – Algorithms & Data Structures
COMP7505 – Equivalent Course(s)
Course Profile
Version
This is version 1.0 of the COMP2502 course profile, dated 5 July 2004.
Changes since the last version
None
Course Summary
| Course Code(s): | COMP2502 |
| Unit Value: | #2 |
| Contact Hours: | 4 hours per week (3L1T) |
| Purpose: | COMP2502 is about the basic fundamental data structures and algorithms which form the basis of large complex software systems. This course builds an understanding of the storage mechanisms of computers and how to manipulate storage in order to create efficient programs. This knowledge is used to guide the selection of an appropriate structure for a complex system. |
Teaching Staff
Dr Kevin Gates (Course Coordinator)
Office: 69-709
Phone: 53261
Fax: (07) 3365-4999
Email: keg[at]itee.uq.edu.au
Consultation Time:
Note: If you are calling from outside the University follow the appropriate instructions for each location below.
| University of Queensland (St Lucia) indial |
(07) 336 5xxxx or (07) 334 6xxxx |
| Ipswich Campus indial | (07) 338 1xxxx |
Tutors
To be assigned.
Course Goals
This course will build an understanding of how the architecture of a computer inpacts on the construction of programs and how data structures and algorithms can be constructed to efficiently perform desired functionality. The goal of this course is to build enough understanding of data structures and associated algorithms so that an appropriate set can selected in the design of a new software. The students should develop an understanding of:
- Actual computer data structures and how they impact on computer programs;
- Fundamental algorithms and data structures;
- Standard algorithms and data structures including and their time and space requirements;
- The performance implications of alternative implementations of simple abstract data types;
- The selection of appropriate data structures and algorithms for standard problems;
- Object oriented implementation of algorithms and data structures including
standand templates or classes;
- How to appropriately adapt or invent new algorithms and data structures for software engineering problems.
It is expected that upon successful completion of the course, students will
be able to select and implement in a object orientated language an appropriate
set of algorithms and data structures for standard problems.
Graduate Attributes Developed
The University of Queensland has defined a set of graduate attributes to specify broad core knowledge and skills associated with all undergraduate programs (http://www.uq.edu.au/hupp/contents/view.asp?s1=3&s2=20&s3=5). This course addresses these attributes as follows:
| Attribute | Contributions from this Course |
|---|---|
| In-depth knowledge of the field of study | This course will develop in depth knowledge of the fundamental algorithms and data structures that are at the core of any complex software systems. |
| Effective Communication | The ability to collect, analyse and organise information and ideas and
to convey those ideas clearly and fluently, in both written and spoken forms. The ability to engage effectively and appropriately with information technologies |
| Independence and Creativity | The ability to work and learn independently. The ability to identify problems, create solutions, innovate and improve current practices. |
| Critical Judgement | The ability to analyse a complex software problems and identify the appropiate data structures for implementation. |
| Ethical and Social Understanding | The ability to work in a complex social environment both individually and as part of a team structure. |
Assumed Background
Pre-requisites: COMP1500 / IENV1802 + MATH1061+ COMP2500 / IENV1201 (or equivalents)
Students are expected to
- be able to program in Java, based on understanding of basic constructs, control constructs, arrays, methods, objects, classes, inheritance and exceptions
- understand basic logic and set theory, with a solid understanding of fundamental mathematics, including exponents, logarithms and probability
Incompatible: COMP7505 or CS210 or 219 or 282
Resources
Course Profile Copy
In the first lecture (or class meeting) students will be directed to the web address at which this course profile can be read. Students enrolled at St Lucia who wish to retain a hard copy of the profile can use the free print quota provided each semester to students enrolled in courses in the School of Information Technology & Electrical Engineering. For information on how to use this print quota, see the School Policy on Student Photocopying and Printing (St Lucia). Students enrolled at the Ipswich campus will either be provided with a hard copy or given directions in class on how to obtain a free copy.
Textbook
The required/recommended/suggested text is
Preiss, Bruno; Data Structures and Algorithms with Object-Orientated Design Patterns in Java, John Wiley & Sons, Inc., 2000.
Author, Title, Publisher, year.
Reference Texts
In the first lecture (or class meeting) students will be informed of other recommended and reference texts. These texts will also be posted on the web site http://www.itee.uq.edu.au/~comp2505
Handouts
In the first lecture (or class meeting) students will be directed to the web
address for this course at which electronic copies of handouts can be obtained.
Facilities
There will be no special access to a computer lab for this course. Please see the ITEE Student Guide 2003 for information on expectations and requirements for the use of the computer labs.Consultation
Teaching Staff will be available for appointment. Please contact the staff by email and arrange a time to meet with the appropriate staff member.Distribution of Notices
Notices for students in this course will be posted on the course web page. The web page should be checked at least weekkly by each student of the class.
Web
The course web site is available at http://www.itee.uq.edu.au/~comp2502. The course web site will contain will contain the course profile, a notice board and electronic copies of any handouts, additional material and lecture notes.
Newsgroup
The course newsgroup is uq.itee.comp2502. This group is available on both the University and School news servers (news.uq.edu.au and news.itee.uq.edu.au).
Students are free to post questions (and answers!) to the newsgroup. Copies of announcements will also be posted to the newsgroup. The teaching staff will monitor the newsgroup.
Teaching Activities
Lectures
- There are two lectures each week:
- Lecture 1:
- Thursday 8-9 in 24-S304
- Lecture 2:
- Friday 10-12 in 50-3
Tutorials
Students should sign-up (via mySI-net) for a weekly tutorial session (commencing in week 2). Tutorials will be used to reinforce understanding of the course material. Active student participation is expected. The available tutorial sessions are listed below (subject to change).
| Tutorial | Day | Time | Room |
|---|---|---|---|
| Ta | Monday | 3-4pm | 78-224 |
| Tb | Tuesday | 3-4pm | 51-207 |
| Tc | Wednesday | 9-10am | 32-207 |
| Td | Wednesday | 3-4pm | 68-214 |
| Te | Thursday | 9-10am | 78-343 |
| Tf | Thursday | 2-3pm | 76-228 |
| Tg | Friday | 12-1pm | 78-334 |
Attendance
You are not required to attend any of the teaching sessions (except those in which an assessment activity is taking place), however, you are strongly encouraged to do so. The lectures and tutorials have been specifically designed to aid your learning of the course material. Failure to attend a session may result in you being disadvantaged. It is up to you to find out what happened at any class session that you miss.
Teaching Plan
| Week Number | Monday’s Date | Lecture Number | Lecture Topic | Lecture Notes | Tutorials | Assessment | Readings |
|---|---|---|---|---|---|---|---|
| 1 | 26 July | 1 | Admin and Introduction | Admin and Introduction | None | None | Preiss:Appendix and Chapters 1,2 |
| 2 | Algorithm Analysis | Algorithm Analysis | |||||
| 2 | 2 August | 3 | Asymptotic Analysis | Asymptotic Analysis | 1 | None | |
| 4 | Asymptotic Analysis | Asymptotic Analysis | |||||
| 3 | 9 August | 5 | Objectives and Foundational Data Structures | Objectives and Foundational Data Structures | 2 | Assignment 1 (PDF) available as are Java files | None |
| 6 | Abstraction | Abstraction | |||||
| 4 | 16 August | 7 | Abstract Data Types | Abstract Data Types | 3 | None | |
| 8 | Stacks, queues | Stacks, queues | |||||
| 5 | 23 August | 9 | Ordered and Sorted Lists | Ordered and Sorted Lists | 4 | None | |
| 10 | Hashing | Hashing | |||||
| 6 | 30 August | 11 | Hash Tables | Hash Tables | 5 | None | |
| 12 | Trees | Trees | |||||
| 7 | 6 September | 13 | Trees | Trees | 6 | Assignment 1 due Assignment 2 Available |
None |
| 14 | Trees | Trees | |||||
| 8 | 13 September | 15 | Heaps | Heaps | 7 | None | |
| 16 | Priority Queues | Priority Queues | |||||
| 9 | 20 September | 17 | Algorithm Design | Algorithm Design | 8 | None | |
| 18 | Algorithm Design | Algorithm Design | |||||
| 27 September | Mid-semester break (one week) |
||||||
| 10 | 4 October | 19 | Sorting | Sorting | 9 | None | |
| 20 | Sorting Algorithms | Sorting Algorithms | |||||
| 11 | 11 October | 21 | Graphs | Graphs | 10 | None | |
| 22 | Graph Algorithms | Graph Algorithms | |||||
| 12 | 18 October | 23 | Strings | Strings | 11 | Assignment 2 due | None |
| 24 | String Algorithms | String Algorithms | |||||
| 13 | 25 October | 25 | Revision | None | |||
| 26 | Revision | ||||||
| 1 November | Revision Period | ||||||
| Exam Week 1 | 8 November | Final Exam | None | ||||
| Exam Week 2 | 15 November | ||||||
Assessment
COMP2502will be assessed by several methods as outlined below. Your final grade (on a 1 to 7 scale) will be determined by combining the marks from the various assessment components as described below. For each assessment item, reference is made to the specific learning objectives (from the list above) which the assessment item will address.
Assignments
- Actual computer data structures and how they impact on computer programs;
- Fundamental algorithms and data structures;
- Standard algorithms and data structures including and their time and space requirements;
- The performance implications of alternative implementations of simple abstract data types;
- The selection of appropriate data structures and algorithms for standard problems;
- Object oriented implementation of algorithms and data structures including standand templates or classes;
- How to appropriately adapt or invent new algorithms and data structures for software engineering problems.
Assignment 1 will be worth 15% of the final grade and will address the object orientated implementation of stacks, queues, hashing tables and lists as well as basic algorithm asymptotic analysis and space requirements. Students will be expected to apply their understanding of these algorithms by implementing and evaluating the performance of the algorithms on some basic problems. Through the use of these algorithms and data structures an understanding of the advantages and disadvantages will be developed to enable the appropriate selection of a structure and algorithm for a given problem.
Assignment 2 will also be worth 15% of the final grade and will address the object orientated implementation of trees, graphs, text strings. Students will be expected to apply their understanding by implementing and evaluating the performance of the algorithms on some basic problems. Through the use of these algorithms and data structures an understanding of the advantages and disadvantages will be developed to enable the appropriate selection of a structure and algorithm for a given problem.
These assignments will be graded 50% on the success of the implemented algorithms and 50% on the elegance and understanding of the basic principles as evidenced by the solution method chosen, the comments in the code and the analysis of the results when applied to simple problems.
Tutorial Exercises
The tutorial session is the primary consultation time. The 11 weekly tutorials are designed to support the concepts presented in the weekly lectures with further practical exercises which will be posted on the web. It is expected that students will work through the tutorial material attempting to solve as much as possible. During tutorials a peer assessment of the exercises will be conducted from solutions presented and tutors be available to answer further questions. The results of these assessments will be recorded.Final Examination
A two hour final examination will be held during the final examination period. This exam will be closed-book and will contain multiple-choice questions. Programmable calculators and other computing or communication devices are NOT permitted. You will require a HB or 2B pencil and an eraser to complete the exam.
The exam will assess the following course objectives:
- recalling fundamental principles of algorithm and data structures;
- understanding how standard algorithms and data structures work, and their time and space requirements;
- understand the performance implications of alternative implementations of simple abstract data types;
- choosing appropriate data structures and algorithms to solve standard problems;
- relating algorithms and implementations in standard object oriented languages.
Other Requirements
There are no other requirements in addition to the assignments and the final examination for passing this course.
Determination of Final Grade
In order to pass this course, you must pass the final examination (i.e., get 50% or better for it). The final mark will be determined by adding 15% times the mark in each of the two assignments, 10% by the total tutorial score and 60% times the mark for the final exam.
Students who obtain a mark greater than or equal to 75% overall will be awarded a grade of 6.
Students who obtain a mark greater than or equal to 65% overall will be awarded a grade of 5.
Students who obtain a mark greater than or equal to 50% overall will be awarded a grade of 4.
If a student obtains a mark less than 50% overall, or less than 50% for the final examination, a failing grade will be awarded.
Assessment Policies
Submission
Submission of the assignments will be via the online submission system at www.itee.uq.edu.au. There will normally be only a short grace period so that submissions from overloaded machines will not be rejected. It is recommended that you submit your assignments before the due date and time.
Late Submission
Any late submissions of assignments will also be submitted to the online submission system. Except in the case of approved extensions submitted per email to the course email all late submissions will not be graded.
Return of Assignments
The assessment results including any comments will be made available to students in a manner to be announced in the lectures.
Academic Merit, Plagiarism, Proper Referencing, Collusion and Other Misconduct
The School and the wider academic community in general takes academic integrity and respect for other persons and property very seriously. In particular, the following behaviour is unacceptable:
- Submission of plagiarised work, i.e. work that contains content copied from an unacknowledged source.
- Submission of work without academic merit, i.e. work that adds little or nothing to material available from reference sources such as textbooks, websites, etc., even where this is appropriately acknowledged.
- Engaging in collusive behaviour, i.e. inappropriate working together with other students where individual work is required, or working with people outside your team where team work is required.
- Copying work done by other students.
- Failing to adhere to the School’s regulations concerning behaviour in laboratories, in particular occupational health and safety regulations.
Penalties for engaging in unacceptable behaviour can range from cash fines
or loss of grades in a subject, through to expulsion from the University.
You are required to read and understand the School Statement on Misconduct,
available on the ITEE website at: http://www.itee.uq.edu.au/about_ITEE/policies/student-misconduct.html. This
Statement includes advice and links to other sites on how to properly cite references
and other sources in your submissions and on acceptable levels of collaboration.
If you have any questions concerning this statement, please contact your
lecturer in the first instance.
Assessment Feedback
Timely feedback on all progressive assessment in this course will be available in accordance with University policy (HUPP 3.30.6 Student Access to Feedback on Assessment). This feedback will be available from comments on the web pages about the submission and through consulation with the lecturer and tutors.
Students wishing to view examination answer scripts and/or question papers should consult with the School office (Room 217, General Purpose South Building [78], St Lucia; Room 218, Building 1, Ipswich) regarding arrangements.
It is a student’s responsibility to incorporate feedback into their learning; making use of the assessment criteria that they are given; being aware of the rules, policies and other documents related to assessment; and providing teachers with feedback on their assessment practices.
Support for Students with a Disability
Any student with a disability who may require alternative academic arrangements in the course is encouraged to seek advice at the commencement of the semester from a Disability Adviser at Student Support Services.