Course syllabus

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:

• Lecturer (part 1, weeks 1-6)  and Course Coordinator:

Tanya Gvozdeva, room 303s-467, t.gvozdeva@auckland.ac.nz

Office hours:

• Thursday (Oct 31) 11-1
• Friday (Nov 1) 11-1
• Monday (Nov 4) 11-1
• Tuesday (Nov 5) 11-1
• Wednesday (Nov 6) 11-1

• Lecturer (part 2, weeks 7-12):

Michael J. Dinneen, room 303-425, mjd@cs.auckland.ac.nz

Office hours: Tues 1pm-4pm, Wed 2pm-4pm.

• Tutor (weeks 2-12):

Alec Henderson, room 303s-587, ahen386@aucklanduni.ac.nz

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

Class representatives:

You can share with them any suggestions/complains/remarks about the lectures. Please note, the class reps are not a part of the teaching team. They only help us to keep in touch with our students. They cannot answer questions about the course.

Songyan Teng:  sten187@aucklanduni.ac.nz 

Xian Ming Lim: xlim951@aucklanduni.ac.nz 

Dan Richards: dric372@aucklanduni.ac.nz

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)

Piazza:

We have set up Piazza for this course. The main purpose of Piazza is for you to interact with other students in the course; while lecturers will monitor Piazza and help if necessary, we believe that the best way for Piazza to work in this class is if you are all collectively responding to each other's problems! 

In general: mathematics is something that is best learned by doing and then having others critique your working so that you can get better.  As lecturers, students often ask us for extra practice problems, or for the best way to revise material: I claim that Piazza is this!  Try to ask 1-3 questions a week and try to comment on 1-3 posts a week, and I guarantee your skills will improve.

To encourage student responses, we as lecturers will follow a "2 hour" rule: during the first two hours of any post about the material in CS220, we will not respond.  (Note: this does not mean that we will respond immediately after two hours!  Depending on when your question goes up, we may be in meetings, or it may be after work hours and we're trying to take care of our families, etc.  In general, we'll get responses up as soon as is reasonable.  If you haven't seen a response in two working days, please repost or email us.)

Lectures times and locations:

Wednesday, MLT1/303-G23	11am - 12pm
Thursday, Eng1401/401-401	12pm-1pm
Friday, Eng1401/401-401	2pm-3pm

Tutorials:

Tutorials are weekly.  There is one one-hour tutorial each week that you are responsible for attending. Tutorials start in week 2 of the semester. There will be 11 tutorials in total.   

Pre-recorded videos:

Mark Wilson and David Welch have prepared short introductory video lectures which are available from Mark's Youtube channel and David's Youtube channel.

Coursebook:

A coursebook.pdf has been prepared for this class. Hard-copies will be available from the Science Student Resource Centre at a cost of $10. 

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)
• 20% written midterm test
• 50% written final examination
• The test and exam will consist of multiple-choice answers on teleforms.
• COMPSCI 220 has a separate pass requirement, i.e., you will need to pass both the theory (test+exam) and the practical (assignments) individually. 
• We use the standard university grade boundaries. >89.5 for A+, then 5 mark increments down to >49.5 for C-.

Assignments: 

Assignments will be due on the following days:

• Assignment 1 is due on Friday, August 9th, 11:59pm. 
• Assignment 2 is due on Monday, September 16th,  11:59pm. 
• Assignment 3 is due on Friday, October 4th,  11:59pm. 
• Assignment 4 is due on Friday, October 25th,  11:59pm.
  

Late assignments will not be marked.

Please carefully read assignment instructions before submitting. 

Mid-Semester Test:

The Mid-Semester Test is 50 minutes long and covers all of the material from the first six weeks of class.  Check the assignment page and/or your Canvas announcements for locations, times, and more information

Exam:

The Exam is two hours long and covers material from the whole course; it will contain 40 multi-choice questions. The exact date of the exam is not available until around the middle of the semester.

No calculators are permitted on the exam or test. Please note that the test and exam are designed so that a calculator is unnecessary; if you can add and multiply single-digit numbers, you will be capable of performing any of the calculations present.

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 assisting others to cheat, and views cheating in coursework as a serious academic offense. 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 computerized detection mechanisms. Upon a 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.