Department of Computing

Local Navigation

• Comp Home

Unit Outline: COMP225

Semester 1, 2008

Convenor: A. McIver

Prerequisites: COMP125(P) or COMP165(P) and MATH135 (P).

Students should read this unit outline carefully at the start of semester. It contains important information about the unit. If anything in it is unclear, please consult one of the teaching staff in the unit.

About This Unit

The objective of this unit is for students to learn about a wider range of algorithms and data structures, and equally importantly to know which one is the most appropriate for a given situation. Students should finish this unit knowing how to write better, more correct programs through understanding rather than trial-and-error. Topics include but are not limited to sorting and hashing; heaps, priority queues, and the data structures of the C++ STL; binary search trees, 2-3 trees, and extensions; graphs; different styles of algorithm, such as divide-and-conquer and dynamic programming; and the complexity of algorithms. Programming will in the main use the C++ language; some acquaintance with the Unix operating system will be advantageous, but is not required (see below).

COMP225's topics have been designed to give students access to a greater awareness of the software technology underlying most modern computer-based applications, and in particular an appreciation of the impact of performance requirements. It is also essential for several of the Bachelor degree programmes, and forms a prerequisite for a number of 300 level units.

Teaching Staff

Role	Name	Email	Room	Office hours
Convenor, Lecturer	A. McIver	anabel@ics.mq.edu.au	E6A379	Monday 1-3
Lecturer	R. Ballantyne	ros@ics.mq.edu.au	E6A313	Wednesday 1-3

All emails related to COMP225 should be sent to comp225-admin@ics.mq.edu.au and must include your full name and your student id number.

Classes

Each week you should attend 3 hours of lectures, a one hour tutorial and a one hour practical. For details of days, times and rooms consult the timetables webpage.

Note that Practicals commence in week 1 with some short exercises on introducing Unix, and Tutorials commence in week 2 .

You should have selected a tutorial and a practical at enrolment. You should attend the tutorial and practical you are enrolled in. If you do not have a class, or if you wish to change one, you should see the enrolment operators in the E7B courtyard during the first two weeks of the semester. Thereafter you should go to the Student Centre.

Please note that you will be required to attend most of the tutorials and hand in prepared work each week. Failure to do so may result in you failing the unit or being excluded from the exam.

Required and Recommended Texts

The textbook for C++ programming used this semester is:

• Carrano, Data Abstraction and Problem Solving in C++ ,EDITION 4 or 5, Addison Wesley.

This textbook is available from the University Co-op Bookshop.

There is also a companion website by the publisher at www.course.com (look under "Carrano"). This site contains additional information and learning material.

Additional reading that you may find useful for this unit:

• J. Hubbard, Data Structures with C++ (One of Schaums' "Outline series" of Solved Problems.)

Unit Web Page

The web page for this unit can be found at http://www.comp.mq.edu.au/units/comp225 and http://learn.mq.edu.au/. Note that the majority of the unit materials are publicly available while some material requires you to log in to Blackboard CE6 to access it.

The unit will make use of discussion boards hosted within Blackboard CE6. Please post questions there, they will be monitored by the staff on the unit.

Learning Outcomes

A student completing the unit should have:

1. be able to write better, more correct programs through understanding rather than trial-and-error.
2. be familiar with a variety of algorithm design techniques and understand how they can improve either efficiency or clarity.
3. be familiar with the complexity of algorithms and understand their performance issues.
4. be aware of the importance of correctness for iterative and recursive algorithms.
5. be very familiar with trees and graphs and their applications.

In addition to the discipline-based learning objectives, all academic programs at Macquarie seek to develop students' generic skills in a range of areas. One of the aims of this unit is that students develop their skills in the following:

• ability to apply problem-solving skills to both familiar and unfamiliar problems.
• independent learning skills.
• ability to perform time management for themselves and to meet deadlines.
• knowledge of own strengths and weaknesses.
• self-discipline and motivation.
• an awareness and appreciation of ethical issues and professional standards and conduct.

Teaching and Learning Strategy

COMP225 is taught via lectures, tutorials and practical sessions in the laboratory. Lectures are used to introduce new material, give examples of the use of programing methods and techniques and put them in a wider context. While lectures are largely one to many presentations, you are encouraged to ask questions of the lecturer to clarify anything you might not be sure of. Tutorials are small group classes which give you the opportunity to interact with your peers and with a tutor who has a sound knowledge of the subject. You will be given problems to solve each week prior to the tutorial; preparing solutions is important because it will allow you to discuss the problems effectively with your tutor and maximise the feedback you get on your work. The aim of the tutorials is to help develop problem-solving skills and teamwork, and you will be expected to work on problems in class. Practical classes give you an opportunity to practice your programming skills under the supervision of a practical demonstrator. Each week you will be given a number of problems to work on; it is important that you keep up with these problems as doing so will help you understand the material in the unit and prepare you for the work in assignments.

Each week you should:

• Attend lectures, take notes, ask questions.
• Attend your tutorial, seek feedback from your tutor on your work, and hand in any compulsory solutions.
• Attend the practical session, do as many of the practical problems as you can and seek feedback from the practical demonstrator on your work, and hand in any compulsory exercises.
• Read appropriate sections of the text, add to your notes and prepare questions for your lecturer or tutor.
• Prepare answers to next week's tutorial questions.
• Work on any assignments that have been released.

Lecture notes will be made available each week but these notes are intended as an outline of the lecture only and are not a substitute for your own notes or the textbook.

Topic List

Relationship Between Assessment and Learning Outcomes

1. Improved problem solving skills and enhanced ability to think algorithmically: all assessment tasks involve problems solving and analysis and many of the problems involve algorithmic solutions.
2. Significant experience with a modern programming language such as Eiffel, Java or C++: All programming is done in C++.
3. An understanding of the importance of documentation, testing, readability and modularity of programs: these aspects are taking into account in the marking of the three assignments.
4. An understanding of the concepts of interface and implementation of routines...: All written assignments involve interpreting interface specifications and developing implementations. Various abstract data types will form the basis of the three assignments as well as a number of tutorial problems. The exam will cover these concepts in detail.
5. Awareness of some important, well known algorithms, and data structures, including those for trees and graphs, and a good knowledge of the concepts of algorithm correctness and complexity: Using or developing algorithms studied in lectures or tutorials, and their correctness and complexity will feature in the exam.
6. An understanding of recursion over tree and graph structures: one assignment will involve writing programs featuring trees and one will involve writing programs featuring graphs.
7. An undertanding of how program performance (time efficiency) can be improved by storing values in tables, how sorting can be affected by choice of algorithm will feature in tutorials, the written exam and the test.
8. An understanding of tree and/or graph algorithms including their related data structures will be studied in lectures, tutorials and assignments, and will appear in the written exam and the test.

Task	Planned Date	Total Marks
Tutorial Exercises	Weekly	5%
Assignment 1: Dynamic classification (part 1)	Due Week 4	5%
Mid-term test	TBA	5%
Assignment 2: Dynamic classification (part 2);	Due Week 7	10%
Assignment 3: Graphs	Due Week 11	10%
Final Examination	TBA	65%

Your final grade will depend on your overall performance, but note that your performance in each part separately will also be taken into account. In particular:

• You must perform satisfactorily in the examination and test combined in order to pass this unit (gain a P grade). In particular your answers must show that you are able to understand the algorithms studied in lectures and assignments.
• You must submit a reasonable attempt to all three assignments to pass this unit (gain a P grade). This means that your submitted code must compile and be demonstrably correct for a proportion of the programming problems.
• You must submit (in hardcopy) a reasonable attempt to at least 6 tutorials to pass this unit (gain a P grade).
• You must submit (via Blackboard CE6 myAssignment) a reasonable attempt to at least 6 practical exercises to pass this unit (gain a P grade).

All assignments should be handed in via the online Blackboard CE6 system at http://learn.mq.edu.au/ by the time specified in the assignment description. Tutorial questions should be submitted by students in hard copy to the tutor during the tutorial. The tutors will not accept any tutorial work unless it belongs to the student, and only if it is handed in during the tutorial. (Please do not give solutions to tutors at any other time.)

All work submitted should be readable and well presented. For advice on code formatting, please refer to COMP125 code guidelines. (Note that we use the same code guidelines as for COMP125.)

Late work will be accepted with a penalty of 10% of the marks for the assignment per day submitted late. Hence, an assignment submitted five days late will get at most half the marks. If you cannot submit on time because of illness or other circumstances, please contact the lecturer before the due date.

Examinations

The university examination period in First Half year 2008 begins on 10 June and lasts for approximately 2 weeks.

You are expected to present yourself for examination at the time and place designated in the University Examination Timetable. The timetable will be available in Draft form approximately eight weeks before the commencement of the examinations and in Final form approximately four weeks before the commencement of examinations.

You are advised that it is Macquarie University policy not to set early examinations for individuals or groups of students. All students are expected to ensure that they are available until the end of the teaching semester, that is the final day of the official examination period.

The only exception to not sitting an examination at the designated time is because of documented illness or unavoidable disruption. In these circumstances you may wish to consider applying for Special Consideration. Information about unavoidable disruption and the special consideration process is available on the web (PDF).

If a Supplementary Examination is granted as a result of the Special Consideration process the examination will be scheduled after the conclusion of the official examination period. For details of the Special Consideration policy specific to the Department of Computing, see the Department's policy page.

Plagiarism

Please refer to the Department of Computing Plagiarism Policy for the definition of plagiarism, advice on avoiding it and the penalties in place if you are found to have submitted plagiarised work.

University Policy on Grading

Academic Senate has a set of guidelines on the distribution of grades across the range from fail to high distinction. Your final result will include one of these grades plus a standardised numerical grade (SNG).

On occasion your raw mark for a unit (i.e., the total of your marks for each assessment item) may not be the same as the SNG which you receive. Under the Senate guidelines, results may be scaled to ensure that there is a degree of comparability across the university, so that units with the same past performances of their students should achieve similar results.

It is important that you realise that the policy does not require that a minimum number of students are to be failed in any unit. In fact it does something like the opposite, in requiring examiners to explain their actions if more than 20% of students fail in a unit.

Student Support Services

Macquarie University provides a range of Academic Student Support Services. Details of these services can accessed at http://www.student.mq.edu.au.

Staff-Student Liaison Committee

The Department has established a Staff-Student Liaison Committee at each level (100, 200, 300) to provide all students studying a Computing unit the opportunity to discuss related issues or problems with both students and staff.

For each meeting, an agenda is issued and minutes are taken. These are posted on the web at:

• http://www.comp.mq.edu.au/units/200-liaison

Details of the regular meeting dates will be posted on the unit home page. Anyone with an interest in Computing units may attend. This includes staff involved in the teaching and administration of the units, and all students currently taking a Computing unit at that level. There are formal Liaison Committee representatives for each unit who attend to present the views of the student body; all students are welcome and are encouraged to attend.

The meetings are usually held in the Department of Computing Meeting Room, E6A357.

To forward agenda items or get in touch with your representative, send an email to comp225liaison@ics.mq.edu.au.

If you have exhausted all other avenues, then you should consult the Director of Teaching (Dr Steve Cassidy) or the Head of Department (Assoc. Prof. Tony Sloane). You are entitled to have your concerns raised, discussed and resolved.

 

Copyright & Site information

• Copyright Macquarie University
• Privacy statement

• CRICOS Provider No 00002J, ABN 90 952 801 237
• Authorised by: HOD