COMP361 (2021) - Design and Analysis of Algorithms
This course examines techniques for developing correct and efficient algorithms for some important classes of problems in Computer Science. It explores methods for designing algorithms, including greedy algorithms, divide and conquer, dynamic programming and graph algorithms. It covers techniques for demonstrating the correctness of algorithms and for analysing their efficiency.
Course learning objectives
Students who pass this course will be able to:
- Describe some important categories of algorithms
- Design an appropriate algorithm for a given problem
- Demonstrate that an algorithm provides a correct solution to a given problem
- Calculate and compare the efficiencies of different algorithms
- Explain the concepts of computational complexity and computability, and how they apply in practice
The course is primarily offered in-person, but there will also be a remote option and there will be online alternatives for all the components of the course for students who cannot attend in-person.
Students taking this course remotely must have access to a computer with camera and microphone and a reliable high speed internet connection that will support real-time video plus audio connections and screen sharing. Students must be able to use Zoom; other communication applications may also be used. A mobile phone connection only is not considered sufficient. The comuputer must be adequate to support the programming required by the course: almost any modern windows, macintosh, or unix laptop or desktop computer will be sufficient, but an Android or IOS tablet will not.
If the assessment of the course includes tests, the tests will generally be run in-person on the Kelburn campus. There will be a remote option for students who cannot attend in-person and who have a strong justification (for example, being enrolled from overseas). The remote test option may use the ProctorU system for online supervision of the tests. ProctorU requires installation of monitoring software on your computer which also uses your camera and microphone, and monitors your test-taking in real-time. Students who will need to use the remote test option must contact the course coordinator in the first two weeks to get permission and make arrangements.
The goal of COMP 361 is to learn how to design correct and efficient algorithms to solve problems. There are two parts to this: finding a correct solution (design), and determining how efficient it is (analysis). To achieve these goals, the course explores various general methods for designing algorithms, for demonstrating their correctness, and for analysing their efficiency. To illustrate the mechanisms and issues involved with each of the methods, we examine a number of well-known algorithms found in computer science and classify them according to the algorithm design technique used to develop them.
Withdrawal from Course
Withdrawal dates and process:
This course will be offered in-person and online. For students in Wellington, there will be a combination of in-person components and web/internet based resources. It will also be possible to take the course entirely online for those who cannot attend on campus, with all the components provided in-person also made available online.
During the trimester there will be two lectures and one tutorial every week.
Student feedback on University courses may be found at: www.cad.vuw.ac.nz/feedback/feedback_display.php
Dates (trimester, teaching & break dates)
- Teaching: 22 February 2021 - 28 May 2021
- Break: 05 April 2021 - 18 April 2021
- Study period: 31 May 2021 - 03 June 2021
- Exam period: 04 June 2021 - 19 June 2021
Set Texts and Recommended Readings
There are no required texts for this offering.
Mandatory Course Requirements
There are no mandatory course requirements for this course.
If you believe that exceptional circumstances may prevent you from meeting the mandatory course requirements, contact the Course Coordinator for advice as soon as possible.
The two tests will take place in the lectures during weeks 6 and 12 respectively. The first 3 assignments will be due during the normal 12 main teaching weeks while assignment 4 will be due towards the end of the "assessment period".
|Assessment Item||Due Date or Test Date||CLO(s)||Percentage|
|Assignments (4) worth 12.5% each||3 due during teaching weeks, one due in Assessment Period||CLO: 1,2,3,4,5||50%|
|Test 1||Week 6||CLO: 1,2,3,4,5||25%|
|Test 2||Week 12||CLO: 1,2,3,4,5||25%|
Policy for Late Submissions:
Each student will have 3 "late days" which you may choose to use for any assignment or assignments during the course. There will be no penalty applied for these late days. You do not need to apply for these - any late days you have left will be automatically applied to assignments that you submit late.
The submission system will give you 72 hours worth of "seconds" to use throughout the five assignments, so this gives you more leeway and it will be automatically calculated and reported to you by the ECS Student Marks system.
After the 3 late days have used up, any assignment submitted up to 24 hours after the deadline will be penalised by 20% of your marks, and any assignment submitted between 24 and 48 hours after the deadline will be penalised by 40% of you marks. Any assignment submitted 48 hours or more after the deadline will not be marked and will get 0 marks.
Individual extensions will only be granted in exceptional personal circumstances, and should be negotiated with the course coordinator before the deadline whenever possible. Documentation (eg, medical certificate) may be required.
Submission & Return
All work is submitted through the ECS submission system, accessible through the course web pages. Marks and comments will be returned through the ECS marking system, also available through the course web pages.
In order to maintain satisfactory progress in COMP 361, you should plan to spend an average of 10 hours per week on this paper. A plausible and approximate breakdown for these hours would be:
- Lectures and Tutorials: 3 hours,
- Readings: 2 hours,
- Assignments: 5 hours.
Communication of Additional Information
All online material for this course can be accessed at https://ecs.wgtn.ac.nz/Courses/COMP361_2021T1/
Links to General Course Information
- Academic Integrity and Plagiarism: https://www.wgtn.ac.nz/students/study/exams/integrity-plagiarism
- Academic Progress: https://www.wgtn.ac.nz/students/study/progress/academic-progess (including restrictions and non-engagement)
- Dates and deadlines: https://www.wgtn.ac.nz/students/study/dates
- Grades: https://www.wgtn.ac.nz/students/study/progress/grades
- Special passes: Refer to the Assessment Handbook, at https://www.wgtn.ac.nz/documents/policy/staff-policy/assessment-handbook.pdf
- Statutes and policies, e.g. Student Conduct Statute: https://www.wgtn.ac.nz/about/governance/strategy
- Student support: https://www.wgtn.ac.nz/students/support
- Students with disabilities: https://www.wgtn.ac.nz/st_services/disability/
- Student Charter: https://www.wgtn.ac.nz/learning-teaching/learning-partnerships/student-charter
- Terms and Conditions: https://www.wgtn.ac.nz/study/apply-enrol/terms-conditions/student-contract
- Turnitin: http://www.cad.vuw.ac.nz/wiki/index.php/Turnitin
- University structure: https://www.wgtn.ac.nz/about/governance/structure
- VUWSA: http://www.vuwsa.org.nz
Offering CRN: 26060
Prerequisites: COMP 261
Duration: 22 February 2021 - 20 June 2021
Starts: Trimester 1