Students
COMP333 – Algorithm Theory and Design
2019 – S2 Day
General Information
Download as PDF
| Unit convenor and teaching staff |
Unit convenor and teaching staff
Convenor
Gaurav Gupta
Contact via Contact via Dialogue Utility
Lecturer (weeks 1-9, 13)
Daniel Sutantyo
Lecturer (weeks 10-12)
Muhammad Ikram
|
|---|---|
| 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 https://www.mq.edu.au/study/calendar-of-dates
Learning Outcomes
On successful completion of this unit, you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
- Improve capability to work collaboratively in a small team.
General Assessment Information
Late Submission
No extensions will be granted without an approved application for Special Consideration. There will be a deduction of 10% of the total available marks made from the total awarded mark for each 24 hour period or part thereof that the submission is late. For example, 25 hours late in submission for an assignment worth 10 marks – 20% penalty or 2 marks deducted from the total. No submission will be accepted after solutions have been posted.
Supplementary Exam
If you receive Special Consideration for the final exam, a supplementary exam will be scheduled after the normal exam period, following the release of marks. By making a special consideration application for the final exam you are declaring yourself available for a resit during the supplementary examination period and will not be eligible for a second special consideration approval based on pre-existing commitments. Please ensure you are familiar with the policy prior to submitting an application. Approved applicants will receive an individual notification one week prior to the exam with the exact date and time of their supplementary examination.
Assessment Tasks
| Name | Weighting | Hurdle | Due |
|---|---|---|---|
| Weekly exercises | 10% | No | 9am every Tuesday (starting from Week 2) |
| In-class tests | 20% | No | Weeks 7 and 13 |
| Assignment 1 | 20% | No | Final deadline: 9am Tuesday, 24 September 2019 |
| Assignment 2 | 20% | No | Final deadline: 9am Tuesday, 12 November 2019 |
| Final Examination | 30% | No | During exam period |
Weekly exercises
Due: 9am every Tuesday (starting from Week 2)
Weighting: 10%
A set of exercises will be made available online every week to be discussed during the workshop, starting from Week 1. You will be expected to attempt and submit a selection of questions for your homework each week.
The homework exercises are to be completed and submitted electronically in the form of a PDF file before the deadline of 9am every Tuesday starting from the second week. Some homework questions may be adapted for the class tests.
For each submission, a mark of out of 1 will be given, and your total mark for this assessment will be the total sum of your submission marks to a maximum of 10 (there may be more than 10 submissions throughout the semester).
On successful completion you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
In-class tests
Due: Weeks 7 and 13
Weighting: 20%
Two in-class tests will be conducted during the Wednesday lecture in weeks 7 and 13. These tests will assess the understanding of the course material from the preceding weeks. The questions should be similar in nature to the ones that will be discussed during the workshops.
Each test contributes 10% to your total assessment for this unit.
On successful completion you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
Assignment 1
Due: Final deadline: 9am Tuesday, 24 September 2019
Weighting: 20%
This assignment will be organised into sub-tasks with different submission deadlines, so there will be multiple deadlines for the different tasks. Please read carefully the details in the assignment specifications when they become available so that you are familiar with the precise submission deadlines.
Some parts of the assignment are to be done individually and others will be completed both individually and collaboratively in a team in order to mimic a real software development project. Each part is to be submitted online on iLearn.
On successful completion you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
- Improve capability to work collaboratively in a small team.
Assignment 2
Due: Final deadline: 9am Tuesday, 12 November 2019
Weighting: 20%
This assignment will also be organised into two or more parts with different submission deadlines which will be detailed in the assignment specification. As in the first assignment, there will be individual tasks and group tasks. Both parts will be submitted online on iLearn. There may be a presentation component in this assignment.
On successful completion you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
- Improve capability to work collaboratively in a small team.
Final Examination
Due: During exam period
Weighting: 30%
The final examination will be a three-hour examination (closed book) held during the usual University examination period and will cover all topics.
On successful completion you will be able to:
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
Delivery and Resources
CLASSES
Each week you should attend three hours of lectures and a two hour mixed workshop class (that is, a tutorial and a practical combined in a single session). For details of days, times and rooms consult the timetables webpage.
Please note that mixed workshop classes commence in Week 1. You are strongly advised to attend the mixed workshop classes, and you are expected to submit the requested homework by Tuesday 9am in the following week. Please note that the class tests and the final exam will draw upon the weekly homework exercises. You are therefore expected and strongly advised to complete these homework exercises, and to seek clarification when you are unable to complete a question.
Textbooks
The following textbooks are recommended but not required for COMP333:
- (Skiena) 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.
- (CLRS) T. H. Cormen, C. E. Leiserson, R. L. Rivest, & C. Stein, Introduction to Algorithms (MIT Press) 3rd edition. ISBN 0-262-53305-7.
The textbooks are available online via the library website.
Digital recordings of lectures will be made available through Active Learning Platform.
Technology
Object-oriented technology, language and development environment: Eclipse IDE for Java development
Version control: git
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.
Teaching and Learning Strategy
COMP333 is taught via lectures in the lecture theatre and mixed workshop classes in the laboratory. Lectures are used to introduce new theoretical material, to give examples of the use of such material, and to put the core principles and methods into a wider context. Mixed workshop 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 with your tutor and peers thereby making the most of this activity. The aim of the mixed workshop classes is to help you to develop problem-solving skills and teamwork, and you will be expected to work on problems in class. Mixed workshop classes give you an opportunity to practise your programming skills, and to implement many of the ideas discussed in lectures. It is important that you keep up with the problems in your mixed workshop classes as doing so will help you understand the material in the unit and prepare you for your assignments, mid-term test and final exam. Additional questions will be 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
Following is the provisional schedule of topics, which is subject to adjustment.
|
Week |
Topic |
Reading |
Lecturer |
|
1 |
Algorithm Design and Analysis |
CLRS Chapter 1-4, Skiena Chapter 1-2 |
Daniel Sutantyo |
|
2 |
Algorithm Correctness |
Skiena Chapter 1 |
Daniel Sutantyo |
|
3 |
Exhaustive Search |
Skiena Chapter 7 |
Daniel Sutantyo |
|
4 |
Dynamic Programming |
CLRS Chapter 15, Skiena Chapter 8 |
Daniel Sutantyo |
|
5 |
Greedy Algorithms |
CLRS Chapter 16 |
Daniel Sutantyo |
|
6 |
Divide and Conquer Algorithms |
Skiena Chapter 4 |
Daniel Sutantyo |
|
7 |
String Algorithms, In-Class Test 1 |
CLRS Chapter 15 and 32, Skiena Chapter 18 |
Daniel Sutantyo |
|
Recess |
|||
|
8 |
Probabilistic Algorithms |
CLRS Chapter 5 |
Daniel Sutantyo |
|
9 |
Graph Algorithms |
Skiena Chapter 6, CLRS Chapters 24-26 |
Daniel Sutantyo |
|
10 |
Computational Complexity I |
Skiena Chapter 9, CLRS Chapter 34 |
Muhammad Ikram |
|
11 |
Computational complexity II |
Skiena Chapter 9, CLRS Chapter 34 |
Muhammad Ikram |
|
12 |
Computational Complexity III |
Skiena Chapter 9, CLRS Chapter 35 |
Muhammad Ikram |
|
13 |
Revision, In-Class Test 2 |
Daniel Sutantyo |
Policies and Procedures
Macquarie University policies and procedures are accessible from Policy Central (https://staff.mq.edu.au/work/strategy-planning-and-governance/university-policies-and-procedures/policy-central). Students should be aware of the following policies in particular with regard to Learning and Teaching:
- Academic Appeals Policy
- Academic Integrity Policy
- Academic Progression Policy
- Assessment Policy
- Fitness to Practice Procedure
- Grade Appeal Policy
- Complaint Management Procedure for Students and Members of the Public
- Special Consideration Policy (Note: The Special Consideration Policy is effective from 4 December 2017 and replaces the Disruption to Studies Policy.)
Undergraduate students seeking more policy resources can visit the Student Policy Gateway (https://students.mq.edu.au/support/study/student-policy-gateway). It is your one-stop-shop for the key policies you need to know about throughout your undergraduate student journey.
If you would like to see all the policies relevant to Learning and Teaching visit Policy Central (https://staff.mq.edu.au/work/strategy-planning-and-governance/university-policies-and-procedures/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/study/getting-started/student-conduct
Results
Results published on platform other than eStudent, (eg. iLearn, Coursera etc.) 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 or if you are a Global MBA student contact globalmba.support@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 Services and 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.
Student Enquiries
For all student enquiries, visit Student Connect at ask.mq.edu.au
If you are a Global MBA student contact globalmba.support@mq.edu.au
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
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
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
Assessment tasks
- Assignment 1
- Assignment 2
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 outcomes
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Improve capability to work collaboratively in a small team.
Assessment tasks
- Assignment 1
- Assignment 2
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
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
Assessment task
- In-class tests
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
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Improve capability to work collaboratively in a small team.
Assessment tasks
- Weekly exercises
- In-class tests
- Assignment 1
- Assignment 2
- Final Examination
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 outcomes
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Improve capability to work collaboratively in a small team.
Assessment tasks
- 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
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Enhance relevant technical skills in order to design and implement algorithms to satisfy specified problem constraints.
- Improve capability to work collaboratively in a small team.
Assessment tasks
- Weekly exercises
- In-class tests
- Assignment 1
- Assignment 2
- Final Examination
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
- Gain advanced algorithmic knowledge in order to tackle concrete problems and provide adapted algorithmic solutions.
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
- Improve capability to work collaboratively in a small team.
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 outcome
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
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 outcome
- Develop ability to communicate clearly and effectively the relevant aspects of algorithms and their performance.
Changes from Previous Offering
- Brute-force algorithms (exhaustive search) are included.
- Arithmetic algorithms have been replaced with graph algorithms.
- Single mid-term test (worth 10%) replaced by two in-class tests (each worth 10%)
- Final exam weight reduced from 40% to 30%. Duration of the exam increased from two hours to three hours to address the analytical nature of the questions.