Unit Outline: COMP225 Algorithms and Data Structures

Semester 1, 2011

Faculty: Science; Department: Computing; Credit points: 3

Convenor:Igor Shparlinski

Prerequisites: (COMP125(P) or COMP165(P)) and (3cp(P) from MATH132-MATH136 or DMTH137).

Format

• 2 hours of lectures
• 2 hours of mixed classes - students should enrol in a 2 hour mixed class session
• You will be asked to perform experiments in your mixed classes, and to compile results of performance. These results should be put together in a "portfolio" of work which will be collected and marked periodically throughout the semester. Please follow the instructions carefully during your work. The portfolios will contribute to your final practical.

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.

Unit Description

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 algorithms and data structures 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
Convenor, Lecturer	Igor Shparlinski	igor.shparlinski@mq.edu.au	E6A382
Lecturer	Mark Dras	mark.dras@mq.edu.au	E6A380

All emails related to COMP225 must include your full name and your student id number.

Technology required

C++ compiler.

Classes

Each week you should attend 2 hours of lectures and a two hour of mixed classes. For details of days, times and rooms consult the timetables webpage.

Note that mixed classes in week 1 with some short exercises on introducing Unix .

You should have selected one two-hour mixed classes session at enrolment. You must attend the session you are enrolled in.

Please note that you are expected to attend most of the mixed classes and required to submit work by the stated deadlines. 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.)
• R. Sedgewick, Algorithms in C++

Unit Web Page

The web page for this unit can be found at http://www.comp.mq.edu.au/units/comp225/. Note that the majority of the unit materials are on moodle.

The unit will make use of discussions hosted within moodle. Please post questions there, they will be monitored by the staff on the unit.

Learning Outcomes

1. Learning Outcome #1 : Algorithm correctness, analysis and design A student completing the unit should :
   • be familiar with a variety of algorithm design techniques and understand how they can improve either efficiency or clarity.
   • be familiar with the complexity of algorithms and understand their performance issues.
   • be aware of the importance of correctness for algorithms.
2. Learning Outcome #2 : Data Structures and their applications A student completing this usit should:
   • be very familiar with trees and their applications
   • be very familiar with graphs and their applications
   • be familiar with maps, hash tables, lists and other commonly used data structures.
   • be able to choose an appropriate data structure for a given application.
3. Learning Outcome #3 : Program Development A student completing this unit should:
   • be able to write better, more correct programs through understanding rather than trial-and-error.
   • be able to apply their knowledge of data structures to writing more efficient programs in c++.
   • have an understanding of the importance of documentation, testing, readability and modularity of programs

Graduate Skills

In addition to the discipline-based learning objectives, all academic programs at Macquarie seek to develop students' graduate capabilities 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 and mixed classes in the laboratory. Lectures are used to introduce new theoretic material, give examples of the use these techniques and put them in a wider context. Mixed classes give you the opportunity to interact with your peers. You will be given problems to solve each week prior to each session; 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 mixed classes is to help you to develop problem-solving skills and teamwork, and you will be expected to work on problems in class. Mixed classes give you an opportunity to practice your programming skills, and to implement many of the ideas discussed in lectures. 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. Some of the questions are designated compulory and they contribute to your total garde. These must be completed and submitted but the deadline.

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 (Preliminary)

Assessment Standards

COMP225 will be graded according to the following general descriptions of the letter grades as specified by Macquarie University. Note that the Conceded Pass (PC) Grade has been abandoned in 2011

• High Distinction (HD, 85-100): provides consistent evidence of deep and critical understanding in relation to the learning outcomes. There is substantial originality and insight in identifying, generating and communicating competing arguments, perspectives or problem solving approaches; critical evaluation of problems, their solutions and their implications; creativity in application.
• Distinction (D, 75-84): provides evidence of integration and evaluation of critical ideas,principles and theories, distinctive insight and ability in applying relevant skills and concepts in relation to learning outcomes. There is demonstration of frequent originality in defining and analysing issues or problems and providing solutions; and the use of means of communication appropriate to the discipline and the audience.
• Credit (Cr, 65-74): provides evidence of learning that goes beyond replication of content knowledge or skills relevant to the learning outcomes. There is demonstration of substantial understanding of fundamental concepts in the field of study and the ability to apply these concepts in a variety of contexts; plus communication of ideas fluently and clearly in terms of the conventions of the discipline.
• Pass (P, 50-64): provides sufficient evidence of the achievement of learning outcomes.There is demonstration of understanding and application of fundamental concepts of the field of study; and communication of information and ideas adequately in terms of the conventions of the discipline. The learning attainment is considered satisfactory or adequate or competent or capable in relation to the specified outcomes.
• Fail (F, 0-49): does not provide evidence of attainment of all learning outcomes. There is missing or partial or superficial or faulty understanding and application of the fundamental concepts in the field of study; and incomplete, confusing or lacking communication of ideas in ways that give little attention to the conventions of the discipline

  Relationship Between Assessment and Learning Outcomes

  1. Correctness, Analysis and Design of algorithms all assessment tasks involve problem solving and analysis and many of the problems involve algorithmic solutions.
  2. Data Structures Most assessment tasks involve a choice of data structures
  3. Program Development All practical exercises and programming assignments involve program development.

  Task	Planned Date	Total Marks	Learning Outcomes
  Mixed Classes Exercises	Submitted according to the instructions.	5%	LO#1, LO#2, LO#3
  Assignment 1 :	Due Week 4	5%	LO#1, LO#2, LO#3
  Assignment 2 :	Due Week 8	15%	LO#1, LO#2, LO#3
  Assignment 3:	Due Week 12	15%	LO#1, LO#2, LO#3
  Final Examination	TBA	60%	LO#1, LO#2, LO#3

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

  To be eligible for special consideration at least 5 satisfactory weekly mixed classes submissions and satisfactory submissions for all assignments are required.

  Extension requests: Late work will not accepted. If you cannot submit on time because of illness or other circumstances, please contact the lecturer before the due date.

  Summary of achievement required corresponding to each final grade

  Final Grade	Summary of required performance
  HD and D	Overall the quality of the work demonstrates a mature and considered appreciation of the programming and algorithmic concepts, and an excellent technical mastery of C++ programming (sufficient to complete the advanced programming tasks). A systematic demonstration of the ability to problem solve independently and a thorough knowledge of how to critique the proposed solution, in terms of performance, correctness and other technical issues.
  CR	Overall the quality of the work demonstrates a reasonable appreciation of the programming and algorithmic concepts, and a good technical mastery of C++ programming (sufficient to complete the required programming tasks). A systematic demonstration of the ability to solve basic problems and to present the solutions clearly with an attempt to give reasons why they meet their stated objectives. Some knowledge of how to critique the proposed solution, in terms of performance, correctness and other technical issues is demonstrated, but the answers given might not cover all cases.
  P	The quality of work demonstrates a basic technical mastery of the C++ language, a basic understanding of how to program using the studied algorithms and a knowledge of how to implement and use the basic algorithmic data structures and programming techniques introduced in the course. The assessment work demonstrate a basic understanding of performance and correctness issues relative to all of the algorithms and data structures studied in the unit, and the appropriateness of a particular algorithm relative to a given data structure.

  Assessment Summary

  If you meet the following criteria, you will gain the grade indicated: for example, you will get an HD if you get 85% overall and 85% in the exam

  Grade	Assessment plus Exam	AND	Final Exam
  HD	≥ 85%	AND	≥ 85%
  D	≥ 75%	AND	≥ 75%
  CR	≥ 65%	AND	≥ 65%
  P	≥ 50%	AND	≥ 45%

  Administration

  Macquarie is developing a number of policies in the area of learning and teaching. Approved policies and associated guidelines can be found at Policy Central. Refer to the Science Centre regarding the implementation of these policies (e.g. precise procedures, forms, deadlines, etc).

  Special Consideration

  Special Consideration is intended for a student who is prevented by serious and unavoidable disruption from completing any unit requirements in accordance with their ability. See above for the necessary conditions to be eligible for special consideration. This application form needs to be filled and submitted to the Science centre along with some evidence to support your case. Depending on the circumstances presented, the convenor may choose to give you an alternate assessment, additional time for an assessment, make-up exam, etc.
  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.