COMP361 (2021) - Design and Analysis of Algorithms

Prescription

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:

  1. Describe some important categories of algorithms
  2. Design an appropriate algorithm for a given problem
  3. Demonstrate that an algorithm provides a correct solution to a given problem
  4. Calculate and compare the efficiencies of different algorithms
  5. Explain the concepts of computational complexity and computability, and how they apply in practice

Course content

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:
https://www.wgtn.ac.nz/students/study/course-additions-withdrawals

Lecturers

AProf Alex Potanin (Coordinator)

Dr Aaron Chen

Teaching Format

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

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

Class Times and Room Numbers

22 February 2021 - 14 March 2021

  • Wednesday 09:00 - 09:50 – LT118, Laby, Kelburn
22 February 2021 - 04 April 2021

  • Monday 09:00 - 09:50 – LT118, Laby, Kelburn
  • Thursday 09:00 - 09:50 – LT118, Laby, Kelburn
19 April 2021 - 30 May 2021

  • Monday 09:00 - 09:50 – LT118, Laby, Kelburn
  • Thursday 09:00 - 09:50 – LT118, Laby, Kelburn

Required

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.

Assessment

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 ItemDue Date or Test DateCLO(s)Percentage
Assignments (4) worth 12.5% each3 due during teaching weeks, one due in Assessment PeriodCLO: 1,2,3,4,550%
Test 1Week 6CLO: 1,2,3,4,525%
Test 2Week 12CLO: 1,2,3,4,525%

Penalties

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.

Extensions

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.

Workload

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.

Teaching Plan

See https://ecs.wgtn.ac.nz/Courses/COMP361_2021T1/LectureSchedule

Communication of Additional Information

All online material for this course can be accessed at https://ecs.wgtn.ac.nz/Courses/COMP361_2021T1/

Offering CRN: 26060

Points: 15
Prerequisites: COMP 261
Duration: 22 February 2021 - 20 June 2021
Starts: Trimester 1
Campus: Kelburn