Logo Students

COMP333 – Algorithm Theory and Design

2017 – S2 Day

General Information

Pdf icon Download as PDF
Unit convenor and teaching staff Unit convenor and teaching staff Tutor
David Lewis
Contact via email
Convenor/Lecturer
Annabelle McIver
Contact via Email
E6A 379
Credit points Credit points
3
Prerequisites Prerequisites
(39cp at 100 level or above) including (COMP225 and DMTH237)
Corequisites Corequisites
Co-badged status Co-badged status
Unit description Unit description
This unit covers general issues of the theory of computation and algorithm design, including computability and complexity. The general principles are illustrated by designing several very efficient algorithms with applications in telecommunication networks, cryptography and other important fields.

Important Academic Dates

Information about important academic dates including deadlines for withdrawing from units are available at http://students.mq.edu.au/student_admin/enrolmentguide/academicdates/

Learning Outcomes

  1. Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  2. Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  3. Communicate clearly and effectively relevant aspects of algorithms and their performance
  4. Work collaboratively in small teams

General Assessment Information

The final mark for the unit will be calculated by combining the marks for all assessment tasks according to the percentage weightings shown in the assessment summary.

Extension requests:  Please note if you cannot submit on time because of illness or other circumstances, please contact the lecturer before the due date. If you experience a disruption to studies (http://www.students.mq.edu.au/student_admin/manage_your_study_program/disruption_to_studies/), you should notify the university.  Please note that this is a centralised process, and resolution can take some time.  This may mean, for example, that you are notified that your disruption request has been approved only after any reasonable length extension for an assignment could be granted: for instance, the assignment might have already been handed back.  With respect to assignments, you should therefore also notify the lecturer responsible for the assignment, and submit a solution to the assignment via iLearn, at the same time as you lodge your official disruption notification.  Failure to do so means that an extension may not be possible, leaving only some other remedy listed under the disruption to study outcomes schedule (e.g. partake in assessment task next available session).

If you apply for Disruption to Study for your final examination, you must make yourself available for the week of December 11 – 15,  2017.  If you are not available at that time, there is no guarantee an additional examination time will be offered. Specific examination dates and times will be determined at a later date.

Assessment Tasks

Name Weighting Hurdle Due
Weekly exercises 10% No Week 2 to week 13
In class tests 20% No Weeks 7 & 13
Assignment 1 20% No weeks 5 to 7
Assignment 2 20% No weeks 9 to 13
Final Examination 30% No During Exam period

Weekly exercises

Due: Week 2 to week 13
Weighting: 10%

Each week, a set of exercises will be made available online. A selection of the questions will be discussed during your workshop class. You will be expected to complete a further selection of questions for homework. 

The homeworks are to be completed in pairs and submitted electronically (in the form of a PDF file) before the deadline (usually 11pm every Sunday).  Feedback will be given the following week on the submitted questions; a selection of these questions will be used as a basis for the class tests.


This Assessment Task relates to the following Learning Outcomes:
  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints

In class tests

Due: Weeks 7 & 13
Weighting: 20%

In class tests (typically 40 mins) will assess the understanding of the course material. Questions in the tests will be closely based on a selection of the submitted weekly exercises. Note that "in class test" means the test will take place during scheduled lecture time.

 


This Assessment Task relates to the following Learning Outcomes:
  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions

Assignment 1

Due: weeks 5 to 7
Weighting: 20%

This assignment is organised into sub-tasks. So there are different submission deadlines for this assignment. Each part will be submitted online. Some parts are to be done individually, whereas others will be completed both individually and collaboratively in a team in order to mimic a real software development project and to give you a chance to fully appreciate the advantages of System Design. Please read carefully the details in the assignment specifications when they become available so that you are familiar with the precise submission deadlines.


This Assessment Task relates to the following Learning Outcomes:
  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Assignment 2

Due: weeks 9 to 13
Weighting: 20%

This assignment is organised into sub-tasks. So there are different submission deadlines for this assignment. Each part will be submitted online. Some parts are to be done individually, whereas others will be completed both individually and collaboratively in a team in order to mimic a real software development project and to give you a chance to fully appreciate the advantages of System Design. Please read carefully the details in the assignment specifications when they become available so that you are familiar with the precise submission deadlines.


This Assessment Task relates to the following Learning Outcomes:
  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Final Examination

Due: During Exam period
Weighting: 30%

The final examination will be a two-hour examination (closed book) held during the usual University examination period and will cover all topics.

 


This Assessment Task relates to the following Learning Outcomes:
  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Communicate clearly and effectively relevant aspects of algorithms and their performance

Delivery and Resources

CLASSES

Each week you should attend three hours of lectures, a two hour mixed class (a tutorial and a practical combined in a single session). For details of days, times and rooms consult the timetables webpage.

Please note that Workshops commence in Week 2 and that you are strongly advised to attend the Workshops and hand in prepared work each week.  You will be working in pairs and handing in joint work. Details for how to select your team member will be given in the first week in lectures. Please note that the two in-class quizzes will be strongly based on the weekly exercises. You are therefore strongly advised to complete the set class exercises, and to seek clarification when you are unable to complete a question. The assignments will involve a presentation which will be marked in the relevant workshop; you will be required to attend those workshops to receive credit for the presentation part.

We recommend that during Week 1 you make sure that you can successfully login into your account, and also access unit's materials via iLearn .

REQUIRED AND RECOMMENDED TEXTS AND/OR MATERIALS

Textbooks

The following textbooks are recommend but not required  for COMP333:

  • [1] S. S. Skiena, The Algorithm Design Manual, Springer, 2nd  edition, 2008, ISBN: 978-1-84800-069-8. Electronic version may be available from the library.
  • [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, & C. Stein, Introduction to Algorithms (MIT Press) 3rd edition. ISBN 0-262-53305-7.

They should be available from the University Co-op Bookshop and/or library.

UNIT WEBPAGE AND TECHNOLOGY USED AND REQUIRED

Echo360

http://mq.edu.au/iLearn/student_info/lecture_recordings.htm

Digital recordings of lectures are available. Please follow these instructions to access the recordings.

Technology

Object-oriented technology & languages: Java 

Version control: git/mercurial

Websites

This unit will use iLearn to distribute materials and for submission of work.

Discussion Boards

The unit makes use of discussion boards hosted within iLearn. Please post questions there, they are monitored by the staff on the unit.

Late submissions

No late submissions.

Teaching and Learning Strategy

COMP333 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; preparing solutions is important because it will allow you to discuss the problems effectively with your tutor thereby making the most of this activity. 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 and in class tests.  Additional questions are provided for extension and general practice.

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.

 

Unit Schedule

Week  Topic Reading
1 Introduction to Design and Correctness Chap. 1 in [1]
2 Algorithm analysis, big-oh notation Chap. 2 in [1], Chap 3 in [2]
3 Greedy Algorithms Chap. 8 in [1], Chap. 16 in [2]
4 Dynamic Programming Chap 8 in [1], Chap 15 in [2]
5 String algorithms Chap. 18 in [1], Chap 32 in [2]
6 Graph algorithms I

Chap 5 and 6 in [1], Chap. 6 in [2]

7

In-class test in lectures.

Revision, more graph algorithms.

 
 

Recess 18-29 September

 
8 Graphs algorithms II Chap 5 and 6 in [1], Chap. 6 in [2]
9

Complexity I. Proving hardness

Chap. 9 in [1]
10

Complexity II. Hard problems

Chap. 9 in [1], chap. 34 in [2]
11

Complexity III. Approximating NP-complete problems

Chap. 9 and 16 in [1], chap. 34 and 35 in [2]
12

Complexity IV. Introduction to space complexity

 
13

In-class test in lectures.

Revision.

 

Policies and Procedures

Macquarie University policies and procedures are accessible from Policy Central. Students should be aware of the following policies in particular with regard to Learning and Teaching:

Academic Honesty Policy http://mq.edu.au/policy/docs/academic_honesty/policy.html

Assessment Policy http://mq.edu.au/policy/docs/assessment/policy_2016.html

Grade Appeal Policy http://mq.edu.au/policy/docs/gradeappeal/policy.html

Complaint Management Procedure for Students and Members of the Public http://www.mq.edu.au/policy/docs/complaint_management/procedure.html​

Disruption to Studies Policy (in effect until Dec 4th, 2017): http://www.mq.edu.au/policy/docs/disruption_studies/policy.html

Special Consideration Policy (in effect from Dec 4th, 2017): https://staff.mq.edu.au/work/strategy-planning-and-governance/university-policies-and-procedures/policies/special-consideration

In addition, a number of other policies can be found in the Learning and Teaching Category of Policy Central.

Student Code of Conduct

Macquarie University students have a responsibility to be familiar with the Student Code of Conduct: https://students.mq.edu.au/support/student_conduct/

Results

Results shown in iLearn, or released directly by your Unit Convenor, are not confirmed as they are subject to final approval by the University. Once approved, final results will be sent to your student email address and will be made available in eStudent. For more information visit ask.mq.edu.au.

Student Support

Macquarie University provides a range of support services for students. For details, visit http://students.mq.edu.au/support/

Learning Skills

Learning Skills (mq.edu.au/learningskills) provides academic writing resources and study strategies to improve your marks and take control of your study.

Student Enquiry Service

For all student enquiries, visit Student Connect at ask.mq.edu.au

Equity Support

Students with a disability are encouraged to contact the Disability Service who can provide appropriate help with any issues that arise during their studies.

IT Help

For help with University computer systems and technology, visit http://www.mq.edu.au/about_us/offices_and_units/information_technology/help/

When using the University's IT, you must adhere to the Acceptable Use of IT Resources Policy. The policy applies to all who connect to the MQ network including students.

Graduate Capabilities

Discipline Specific Knowledge and Skills

Our graduates will take with them the intellectual development, depth and breadth of knowledge, scholarly understanding, and specific subject content in their chosen fields to make them competent and confident in their subject or profession. They will be able to demonstrate, where relevant, professional technical competence and meet professional standards. They will be able to articulate the structure of knowledge of their discipline, be able to adapt discipline-specific knowledge to novel situations, and be able to contribute from their discipline to inter-disciplinary solutions to problems.

This graduate capability is supported by:

Learning outcomes

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  • Work collaboratively in small teams

Assessment tasks

  • Weekly exercises
  • In class tests
  • Assignment 1
  • Assignment 2
  • Final Examination

Problem Solving and Research Capability

Our graduates should be capable of researching; of analysing, and interpreting and assessing data and information in various forms; of drawing connections across fields of knowledge; and they should be able to relate their knowledge to complex situations at work or in the world, in order to diagnose and solve problems. We want them to have the confidence to take the initiative in doing so, within an awareness of their own limitations.

This graduate capability is supported by:

Learning outcomes

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  • Work collaboratively in small teams

Assessment tasks

  • Weekly exercises
  • In class tests
  • Assignment 1
  • Assignment 2
  • Final Examination

Creative and Innovative

Our graduates will also be capable of creative thinking and of creating knowledge. They will be imaginative and open to experience and capable of innovation at work and in the community. We want them to be engaged in applying their critical, creative thinking.

This graduate capability is supported by:

Learning outcome

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions

Assessment tasks

  • Assignment 1
  • Assignment 2

Effective Communication

We want to develop in our students the ability to communicate and convey their views in forms effective with different audiences. We want our graduates to take with them the capability to read, listen, question, gather and evaluate information resources in a variety of formats, assess, write clearly, speak effectively, and to use visual communication and communication technologies as appropriate.

This graduate capability is supported by:

Learning outcomes

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Assessment tasks

  • Assignment 1
  • Assignment 2
  • Final Examination

Engaged and Ethical Local and Global citizens

As local citizens our graduates will be aware of indigenous perspectives and of the nation's historical context. They will be engaged with the challenges of contemporary society and with knowledge and ideas. We want our graduates to have respect for diversity, to be open-minded, sensitive to others and inclusive, and to be open to other cultures and perspectives: they should have a level of cultural literacy. Our graduates should be aware of disadvantage and social justice, and be willing to participate to help create a wiser and better society.

This graduate capability is supported by:

Learning outcomes

  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Socially and Environmentally Active and Responsible

We want our graduates to be aware of and have respect for self and others; to be able to work with others as a leader and a team player; to have a sense of connectedness with others and country; and to have a sense of mutual obligation. Our graduates should be informed and active participants in moving society towards sustainability.

This graduate capability is supported by:

Learning outcomes

  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Capable of Professional and Personal Judgement and Initiative

We want our graduates to have emotional intelligence and sound interpersonal skills and to demonstrate discernment and common sense in their professional and personal judgement. They will exercise initiative as needed. They will be capable of risk assessment, and be able to handle ambiguity and complexity, enabling them to be adaptable in diverse and changing environments.

This graduate capability is supported by:

Learning outcome

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions

Assessment tasks

  • Assignment 1
  • Assignment 2

Critical, Analytical and Integrative Thinking

We want our graduates to be capable of reasoning, questioning and analysing, and to integrate and synthesise learning and knowledge from a range of sources and environments; to be able to critique constraints, assumptions and limitations; to be able to think independently and systemically in relation to scholarly activity, in the workplace, and in the world. We want them to have a level of scientific and information technology literacy.

This graduate capability is supported by:

Learning outcome

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions

Assessment tasks

  • Assignment 1
  • Assignment 2
  • Final Examination

Commitment to Continuous Learning

Our graduates will have enquiring minds and a literate curiosity which will lead them to pursue knowledge for its own sake. They will continue to pursue learning in their careers and as they participate in the world. They will be capable of reflecting on their experiences and relationships with others and the environment, learning from them, and growing - personally, professionally and socially.

This graduate capability is supported by:

Learning outcomes

  • Have advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions
  • Possess relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints
  • Communicate clearly and effectively relevant aspects of algorithms and their performance
  • Work collaboratively in small teams

Assessment task

  • In class tests

Changes from Previous Offering

The unit has some changes to the submission of weekly exercises. These will now be organised as a group submission in teams of size two.

There are no hurdle assessments in this offering.

Grading

At the end of the session, you will receive a mark that reflects your achievement in the unit. The final mark for the unit will be calculated by combining the marks for all assessment tasks according to the percentage weightings shown in the assessment summary.

Changes since First Published

Date Description
27/10/2017 Unfortunately the dates for Assignment 2 and the second in class test had to be changed. This is in part due to the external staff having to create new material. I have announced the changes on the forum but I think it important to update the study guide to minimise any possible confusion.