UQ Students should read the Disclaimer & Warning
Note: This page dates from 2005, and is kept for historical purposes.
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<!-- saved from url=(0094)http://www.itee.uq.edu.au/undergraduate/_profile_view.php?print=1&file=2004_2_COMP2502_StLucia -->
<html>
<head>
<title>COMP2502 – Course Profile</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<body>
<h3>The University of Queensland<br />
School of Information Technology and Electrical Engineering<br />
Semester 2, 2004</h3>
<h1>COMP2502 – Algorithms & Data Structures<br />
COMP7505 – Equivalent Course(s)</h1>
<h1>Course Profile</h1>
<h2>Version</h2>
<p>This is version 1.0 of the COMP2502 course profile, dated <b>5 July 2004</b>.</p>
<h3>Changes since the last version</h3>
<p>None</p>
<hr />
<h2>Course Summary</h2>
<table id="AutoNumber6"
cellspacing="1" cellpadding="3" border="1">
<tbody>
<tr>
<td ><b>Course Code(s):</b></td>
<td><b>COMP2502</b> </td>
</tr>
<tr>
<td ><b>Unit Value:</b></td>
<td>#2</td>
</tr>
<tr>
<td ><b>Contact Hours:</b></td>
<td>4 hours per week (3L1T) </td>
</tr>
<tr>
<td ><b>Purpose:</b></td>
<td>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.</td>
</tr>
</tbody>
</table>
<hr />
<h2>Teaching Staff</h2>
<p><b>Dr Kevin Gates (Course Coordinator)</b><br />
Office: 69-709<br />
Phone: 53261<br />
Fax: (07) 3365-4999<br />
Email: keg[at]itee.uq.edu.au<br />
Consultation Time: </p>
<p><small><i>Note: </i>If you are calling from outside the University follow
the appropriate instructions for each location below. </small></p>
<table cellpadding="5" border="0">
<tbody>
<tr>
<td><small>University of Queensland<br />
(St Lucia) indial</small></td>
<td><small>(07) 336 5xxxx<br />
or (07) 334 6xxxx</small></td>
</tr>
<tr>
<td><small>Ipswich Campus indial</small></td>
<td><small>(07) 338 1xxxx </small></td>
</tr>
</tbody>
</table>
<h3>Tutors</h3>
<p>To be assigned.</p>
<hr />
<h2>Course Goals</h2>
<p>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:</p>
<ol>
<li>Actual computer data structures and how they impact on computer programs; </li>
<li>Fundamental algorithms and data structures; </li>
<li>Standard algorithms and data structures including and their time and space
requirements; </li>
<li>The performance implications of alternative implementations of simple abstract
data types; </li>
<li>The selection of appropriate data structures and algorithms for standard
problems; </li>
<li>Object oriented implementation of algorithms and data structures including
standand templates or classes;<br />
</li>
<li>How to appropriately adapt or invent new algorithms and data structures
for software engineering problems. </li>
</ol>
<p>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.<br />
</p>
<h2>Graduate Attributes Developed</h2>
<p>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:</p>
<table id="AutoNumber4"
cellspacing="1" border="1">
<tbody>
<tr>
<th >Attribute</th>
<th >Contributions from this Course</th>
</tr>
<tr>
<td >In-depth knowledge of the field of study</td>
<td >This course will develop in depth knowledge of the fundamental algorithms
and data structures that are at the core of any complex software systems.</td>
</tr>
<tr>
<td >Effective Communication</td>
<td >The ability to collect, analyse and organise information and ideas and
to convey those ideas clearly and fluently, in both written and spoken forms.<br />
The ability to engage effectively and appropriately with information
technologies</td>
</tr>
<tr>
<td >Independence and Creativity</td>
<td >The ability to work and learn independently.<br />
The ability to identify problems, create solutions, innovate
and improve current practices.</td>
</tr>
<tr>
<td >Critical Judgement</td>
<td >The ability to analyse a complex software problems and identify the appropiate
data structures for implementation.</td>
</tr>
<tr>
<td >Ethical and Social Understanding</td>
<td >The ability to work in a complex social environment both individually
and as part of a team structure. </td>
</tr>
</tbody>
</table>
<hr />
<h2>Assumed Background</h2>
<p>Pre-requisites: COMP1500 / IENV1802 + MATH1061+ COMP2500 / IENV1201 (or
equivalents)</p>
<p>Students are expected to</p>
<ul>
<li>be able to program in Java, based on understanding of basic constructs,
control constructs, arrays, methods, objects, classes, inheritance and exceptions </li>
<li>understand basic logic and set theory, with a solid understanding of fundamental
mathematics, including exponents, logarithms and probability </li>
</ul>
It is assumed that students have a basic understanding of the problems associated
with software construction.<br />
<br />
Incompatible: COMP7505 or CS210 or 219 or 282
<hr />
<h2>Resources</h2>
<h3>Course Profile Copy</h3>
<p>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.</p>
<h3>Textbook</h3>
<p>The required/recommended/suggested text is</p>
<blockquote>
<p>Preiss, Bruno; Data Structures and Algorithms with Object-Orientated Design
Patterns in Java, John Wiley & Sons, Inc., 2000.</p>
</blockquote>
<blockquote>
<p>Author, <b>Title</b>, Publisher, year.</p>
</blockquote>
<h3>Reference Texts</h3>
<p>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</p>
<h3>Handouts</h3>
<p>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. <br />
</p>
<h3>Facilities</h3>
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.<br />
<h3>Consultation</h3>
Teaching Staff will be available for appointment. Please contact the staff
by email and arrange a time to meet with the appropriate staff member.<br />
<h3>Distribution of Notices</h3>
<p>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.</p>
<h3>Web</h3>
<p>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.</p>
<h3>Newsgroup</h3>
<p>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). </p>
<p>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. </p>
<hr />
<h2>Teaching Activities</h2>
<h3>Lectures</h3>
<dl>
<dt>There are two lectures each week: </dt>
<dt>Lecture 1: </dt>
<dd>Thursday 8-9 in 24-S304 </dd>
<dt>Lecture 2: </dt>
<dd>Friday 10-12 in 50-3<br />
</dd>
</dl>
<h3>Tutorials</h3>
<p>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).</p>
<table id="AutoNumber1"
cellspacing="0" cellpadding="0" border="1">
<tbody>
<tr>
<th ><b>Tutorial</b></th>
<th ><b>Day</b></th>
<th ><b>Time</b></th>
<th ><b>Room</b></th>
</tr>
<tr>
<td >Ta</td>
<td >Monday</td>
<td >3-4pm</td>
<td >78-224</td>
</tr>
<tr>
<td >Tb</td>
<td >Tuesday</td>
<td >3-4pm</td>
<td >51-207</td>
</tr>
<tr>
<td >Tc</td>
<td >Wednesday</td>
<td >9-10am</td>
<td >32-207</td>
</tr>
<tr>
<td >Td</td>
<td >Wednesday</td>
<td >3-4pm</td>
<td >68-214</td>
</tr>
<tr>
<td >Te</td>
<td >Thursday</td>
<td >9-10am</td>
<td >78-343</td>
</tr>
<tr>
<td >Tf</td>
<td >Thursday</td>
<td >2-3pm</td>
<td >76-228</td>
</tr>
<tr>
<td >Tg</td>
<td >Friday</td>
<td >12-1pm</td>
<td >78-334</td>
</tr>
</tbody>
</table>
<h3>Attendance</h3>
<p>You are not <i>required</i> to attend any of the teaching sessions (except
those in which an assessment activity is taking place), however, you are <i>strongly
encouraged</i> 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.</p>
<h3>Teaching Plan</h3>
<table id="AutoNumber5"
cellspacing="1" border="1">
<tbody>
<tr>
<th >Week Number</th>
<th >Monday’s Date</th>
<th >Lecture Number</th>
<th >Lecture Topic</th>
<th >Lecture Notes</th>
<th >Tutorials</th>
<th >Assessment</th>
<th >Readings</th>
</tr>
<tr>
<td rowspan="2">1</td>
<td rowspan="2">26 July</td>
<td>1</td>
<td>Admin and Introduction </td>
<td>Admin and Introduction </td>
<td rowspan="2"> None</td>
<td rowspan="2"> None</td>
<td rowspan="2">Preiss:Appendix and Chapters 1,2 </td>
</tr>
<tr>
<td>2</td>
<td>Algorithm Analysis</td>
<td>Algorithm Analysis</td>
</tr>
<tr>
<td rowspan="2">2</td>
<td rowspan="2">2 August</td>
<td>3</td>
<td>Asymptotic Analysis</td>
<td>Asymptotic Analysis</td>
<td rowspan="2"> 1</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>4</td>
<td>Asymptotic Analysis </td>
<td>Asymptotic Analysis</td>
</tr>
<tr>
<td rowspan="2">3</td>
<td rowspan="2">9 August</td>
<td>5</td>
<td>Objectives and Foundational Data Structures </td>
<td>Objectives and Foundational Data Structures </td>
<td rowspan="2"> 2 </td>
<td rowspan="2">Assignment 1 (PDF) available as are Java files </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>6</td>
<td>Abstraction</td>
<td>Abstraction</td>
</tr>
<tr>
<td rowspan="2">4</td>
<td rowspan="2">16 August</td>
<td>7</td>
<td>Abstract Data Types</td>
<td>Abstract Data Types</td>
<td rowspan="2"> 3</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>8</td>
<td>Stacks, queues</td>
<td>Stacks, queues</td>
</tr>
<tr>
<td rowspan="2">5</td>
<td rowspan="2">23 August</td>
<td>9</td>
<td>Ordered and Sorted Lists</td>
<td>Ordered and Sorted Lists</td>
<td rowspan="2"> 4 </td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>10</td>
<td>Hashing</td>
<td>Hashing</td>
</tr>
<tr>
<td rowspan="2">6</td>
<td rowspan="2">30 August</td>
<td>11</td>
<td>Hash Tables</td>
<td>Hash Tables</td>
<td rowspan="2"> 5</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>12</td>
<td>Trees</td>
<td>Trees</td>
</tr>
<tr>
<td rowspan="2">7</td>
<td rowspan="2">6 September</td>
<td>13</td>
<td>Trees</td>
<td>Trees</td>
<td rowspan="2"> 6</td>
<td rowspan="2">Assignment 1 due<br />
Assignment 2 Available<br /> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>14</td>
<td>Trees</td>
<td>Trees</td>
</tr>
<tr>
<td rowspan="2">8</td>
<td rowspan="2">13 September</td>
<td>15</td>
<td>Heaps</td>
<td>Heaps</td>
<td rowspan="2"> 7</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>16</td>
<td>Priority Queues</td>
<td>Priority Queues</td>
</tr>
<tr>
<td rowspan="2">9</td>
<td rowspan="2">20 September</td>
<td>17</td>
<td>Algorithm Design</td>
<td>Algorithm Design</td>
<td rowspan="2"> 8</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>18</td>
<td>Algorithm Design</td>
<td>Algorithm Design</td>
</tr>
<tr>
<td> </td>
<td>27 September</td>
<td colspan="6"> <p>Mid-semester break (one week)</p></td>
</tr>
<tr>
<td rowspan="2">10</td>
<td rowspan="2">4 October</td>
<td>19</td>
<td>Sorting</td>
<td>Sorting</td>
<td rowspan="2"> 9</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>20</td>
<td>Sorting Algorithms</td>
<td>Sorting Algorithms</td>
</tr>
<tr>
<td rowspan="2">11</td>
<td rowspan="2">11 October</td>
<td>21</td>
<td>Graphs</td>
<td>Graphs</td>
<td rowspan="2"> 10</td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>22</td>
<td>Graph Algorithms</td>
<td>Graph Algorithms</td>
</tr>
<tr>
<td rowspan="2">12</td>
<td rowspan="2">18 October</td>
<td>23</td>
<td>Strings</td>
<td>Strings</td>
<td rowspan="2"> 11</td>
<td rowspan="2">Assignment 2 due</td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>24</td>
<td>String Algorithms</td>
<td>String Algorithms</td>
</tr>
<tr>
<td rowspan="2">13</td>
<td rowspan="2">25 October</td>
<td>25</td>
<td> Revision</td>
<td> </td>
<td rowspan="2"> </td>
<td rowspan="2"> </td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>26</td>
<td> Revision</td>
<td> </td>
</tr>
<tr>
<td> </td>
<td>1 November</td>
<td colspan="6">Revision Period</td>
</tr>
<tr>
<td>Exam Week 1</td>
<td>8 November</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
<td rowspan="2">Final Exam</td>
<td rowspan="2"> None</td>
</tr>
<tr>
<td>Exam Week 2</td>
<td>15 November</td>
<td> </td>
<td> </td>
<td> </td>
<td> </td>
</tr>
</tbody>
</table>
<hr />
<h2>Assessment</h2>
<p>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. </p>
<h3>Assignments</h3>
<ol>
<li>Actual computer data structures and how they impact on computer programs; </li>
<li>Fundamental algorithms and data structures; </li>
<li>Standard algorithms and data structures including and their time and space
requirements; </li>
<li>The performance implications of alternative implementations of simple abstract
data types; </li>
<li>The selection of appropriate data structures and algorithms for standard
problems; </li>
<li>Object oriented implementation of algorithms and data structures including
standand templates or classes; </li>
<li>How to appropriately adapt or invent new algorithms and data structures
for software engineering problems. </li>
</ol>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<h3>Tutorial Exercises</h3>
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.
<h3>Final Examination</h3>
<p>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.</p>
<p>The exam will assess the following course objectives:</p>
<ul>
<li>recalling fundamental principles of algorithm and data structures; </li>
<li>understanding how standard algorithms and data structures work, and their
time and space requirements; </li>
<li>understand the performance implications of alternative implementations of
simple abstract data types; </li>
<li>choosing appropriate data structures and algorithms to solve standard problems; </li>
<li>relating algorithms and implementations in standard object oriented languages. </li>
</ul>
<h3>Other Requirements</h3>
<p> There are no other requirements in addition to the assignments and the final
examination for passing this course.</p>
<h3>Determination of Final Grade</h3>
<p>In order to pass this course, <i>you must pass the final examination (i.e.,
get 50% or better for it)</i>. 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.</p>
<div style="MARGIN-LEFT: 40px">Students who obtain a mark greater than or equal
to 85% overall will be awarded a grade of 7.<br />
Students who obtain a mark greater than or equal to 75% overall will be awarded
a grade of 6.<br />
Students who obtain a mark greater than or equal to 65% overall will be awarded
a grade of 5.<br />
Students who obtain a mark greater than or equal to 50% overall will be awarded
a grade of 4.<br />
If a student obtains a mark less than 50% overall, or less than 50% for the
final examination, a failing grade will be awarded.</div>
<hr />
<h2>Assessment Policies</h2>
<h3>Submission</h3>
<p> 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.</p>
<h3>Late Submission</h3>
<p>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.</p>
<h3>Return of Assignments</h3>
<p>The assessment results including any comments will be made available to students
in a manner to be announced in the lectures. </p>
<h3>Academic Merit, Plagiarism, Proper Referencing, Collusion and Other Misconduct</h3>
<p>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: </p>
<ul>
<li>Submission of plagiarised work, i.e. work that contains content copied from
an unacknowledged source. </li>
<li>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. </li>
<li>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. </li>
<li>Copying work done by other students. </li>
<li>Failing to adhere to the School’s regulations concerning behaviour in laboratories,
in particular occupational health and safety regulations. </li>
</ul>
<p>Penalties for engaging in unacceptable behaviour can range from cash fines
or loss of grades in a subject, through to expulsion from the University.<br />
<br />
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. <br />
<br />
If you have any questions concerning this statement, please contact your
lecturer in the first instance.</p>
<h3>Assessment Feedback</h3>
<p>Timely feedback on all progressive assessment in this course will be available
in accordance with University policy (HUPP 3.30.6 <i>Student Access to Feedback
on Assessment</i>). This feedback will be available from comments on the
web pages about the submission and through consulation with the lecturer and
tutors. </p>
<p>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.</p>
<p>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.</p>
<hr />
<h2>Support for Students with a Disability</h2>
<p>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. </p>
</body>
</html>