Course syllabus

Jump to today

Welcome to COMPSCI 220 Algorithms and Data Structures.

 

Prerequisites: COMPSCI (105 or 107) and 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 and applications; and graph optimization problems.

 

Course contact hours/timetable

Lectures: Mondays 5-6 pm (109-B15), Thursdays 4-5 pm (303-G23), Fridays 3-4 pm (303-G23).

Tutorials (from week 2) as selected: Mondays 9-10 am and 1-2 pm (114-G10); Wednesdays 9-10 am (114-G14), 12-1 pm (114-G10) and 3-4 pm (114-G17), and Fridays 11 am - 12 pm (105-032). 

 

Contacts

 

Class Reps

 

Contents of the course

We build on the basic data structures from COMPSCI 105/107, using them to implement problem-solving methods called algorithms.

  • Algorithm analysis shows us how to get things done correctly and efficiently. We focus mostly on efficiency in this course -- a good algorithm can make the difference between a program being practically useful or useless. We will learn how to analyse an algorithm for efficiency, and which data structure to use when programming the algorithm. In doing so, we encounter some classic algorithms that today are found everywhere in computing. We'll discuss questions such as: How does your iPod find that song so quickly? Why is Python’s standard sorting algorithm Timsort efficient in application to various types of realistic data?
  • Graphs are natural structures with hugely many applications, and we cover the main concepts and key algorithms. How does Google Maps find the shortest driving distance? How many ways are there to get dressed in the morning? 

 

Learning Outcomes

A student who successfully passes this course should be able to:

  • Express an algorithm's performance using basic asymptotic notation. Predict algorithm performance on large input. Compare performance of various algorithms in a given situation and select the best. 
  • Write a recurrence describing performance of an algorithm given a formal or informal description. Solve that recurrence. 
  • Fluently use computer representations of data structures: lists, trees, dictionaries and graphs. Compare and contrast performance of various data structures for a given problem and select the best one. 
  • Execute and program the fast graph algorithms for standard problems: depth-first and breadth-first search and applications; optimisation problems (e.g. shortest paths, minimum spanning trees). 

 

Textbook

Textbook (recommended): Introduction to Algorithms and Data Structures (3rd electronic edition) by M. J. Dinneen, G. Gimel'farb and M. C. Wilson. The course follows the textbook closely. This free electronic edition of the textbook have been revised and shortened by Dr. Michael Dinneen in line with the current curriculum. 

A copy of the latest version can be found on Canvas under Files.

 

Lecture Recordings

All lectures are recorded.  They may be a delay of 1-2 days before the lecture recordings are distributed through Canvas.  You can find the lecture recordings on the Lecture Recordings page (COMPSCI 107 > Pages > Lecture Recordings).  Note that although the lectures are recorded, some learning activities conducted in class do not translate well to the recordings.  To maximise your learning opportunities, you are encouraged to attend the class in person.

 

Assessment

  • 27% assignments (6 assignments)
  • 13% written midterm test
  • 60% written final examination
  • The test and exam will consist of multiple-choice answers on teleforms (five answer options, one correct answer option per question, no penalties will apply to incorrectly answered questions).
  • The test will cover the material of the first four weeks.
  • All COMPSCI undergraduate courses have a separate pass requirement, i.e., you will need to pass both the test+exam and the coursework components individually. Pass marks for these components will not be higher than half of the available marks in the respective component, but may be adjusted to lower thresholds in individual instances of the course. We therefore recommend that you sit the exam even if you are not confident that you have scored half of the coursework marks.

 

Handling illness or absence

  • If you must leave for family emergencies etc., please talk to the lecturer, or somehow get a message to the department. Very few problems are so urgent that we cannot be told quite quickly.
  • 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).
    THE ONE WEEK LIMIT IS STRICTLY ENFORCED.

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 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 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. 

Help with Canvas

For help with Canvas see: https://www.auckland.ac.nz/en/about/learning-and-teaching/CanvasHomepage/canvas-help---support.html.

Course summary:

Date Details Due