Course syllabus

Jump to today

Welcome to COMPSCI 220 Algorithms and Data Structures.

Prerequisites: COMPSCI (105 or 107 or 130) and (COMPSCI 120 or MATHS (108, or 150 or 153))

Course Description: This course is an introduction to the analysis of algorithms and data structures. Topics covered include: common abstract data types and their implementations; asymptotic complexity analysis; sorting and searching algorithms; depth‐first and breadth‐first search for graphs and applications; and graph optimization problems.

Contacts

Current lecture and tutorial times and venues may be found on Student Services Online.

Learning Outcomes 

  • express a precise relation between two functions using the Big-O, Big-Omega, and Big-Theta notation
  • express an algorithm’s performance using asymptotic notation
  • compare the performance of various algorithms and data structures in a given situation and select the best one
  • write a recurrence describing the performance of an algorithm given a formal or informal description, and solve simple recurrences
  • execute by hand and program advanced sorting algorithms (including heapsort, quicksort, mergesort)
  • execute by hand and program the fast graph algorithms for standard problems: graph traversals and applications; graph optimization problems (e.g. shortest paths, minimum spanning trees)

Lectures

For this semester Mark Wilson has prepared 19 short introductory video lectures which will be available from Mark's Youtube channel and linked on the Lecture recordings page. Students are expected to view the video lecture associated to each lecture, before coming to the relevant lecture period. The lecture period will be used to discuss questions raised by the video lectures or coursebook. The standard lecture recordings made by UoA for these lecture periods will not be very useful, so attendance is very strongly recommended.

Coursebook

A coursebook has been prepared for this class. Hard-copies are available from the Science Student Resource Centre at a cost of $10. We strongly recommend that you bring a hard-copy of the coursebook to lectures with you.

Textbooks

Textbook (required): Introduction to Algorithms and Data Structures. M. J. Dinneen, G. Gimel'farb and M. C. Wilson [DGW] The course follows this free electronic textbook closely.

Textbook (optional): Algorithms 4th Edition. R. Sedgwick and K. Wayne [SW]

Assessment

  • 30% assignments (4 @ 7.5% each)
  • 10% written midterm test
  • 60% written final examination
  • The test and exam will consist of multiple-choice answers on teleforms (one correct answer option per question, and personalized/different for each student).
  • The test (held in usual lecture room) will cover the material of the first five weeks.
  • All COMPSCI undergraduate courses have a separate pass requirement, i.e., you will need to pass both the theory (test+exam) and the practical (programming parts of assignments) individually. 
  • We use the standard university grade boundaries. >89.5 for A+, then 5 mark increments down to >49.5 for C-.

Handling illness or absence

  • For problems affecting assignments or tests, see the lecturer, as soon as reasonably possible.
  • For illness during exams (or other problems that affect exam performance) students must contact the University within one week of the last affected examination, to apply for an aegrotat pass (for illness) or compassionate pass (other problems).

Refer to the University information about Aegrotat and Compassionate Considerations: https://www.auckland.ac.nz/en/for/current-students/cs-academic-information/cs-examination-information/cs-aegrotat-and-compassionate-consideration.html

Academic Integrity

The University of Auckland will not tolerate cheating or the assisting others to cheat, and views cheating in coursework as a serious academic offence. The work that a student submits for grading must be the student's own work, reflecting his or her learning. Where work from other sources is used, it must be properly acknowledged and referenced. This requirement also applies to sources on the world-wide web. A student's assessed work may be reviewed against electronic source material using computerised detection mechanisms. Upon reasonable request, students may be required to provide an electronic version of their work for computerised review.

Please refer to http://www.auckland.ac.nz/uoa/home/about/teaching-learning/honesty.

Harassment

Every member of the University, student or staff, has a right to dignity and respect. Please see the policy on harassment: https://www.auckland.ac.nz/en/for/current-students/cs-student-support-and-services/cs-personal-support/bullying-and-harassment.html. 

 

Course summary:

Date Details Due