Course syllabus

Welcome to COMPSCI 220 Algorithms and Data Structures.

Prerequisites: COMPSCI (105 or 107) and 15 points from MATHS (108, 110, 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; graph optimization problems and string matching.

Contacts

• Lecturer (part 1, weeks 1-5) - Dr Mark C. Wilson, mcw@cs.auckland.ac.nz
• Lecturer (part 2) - Dr David Welch, david.welch@auckland.ac.nz
• Lecturer (part 3) and coordinator - Dr Michael J. Dinneen, room  303-425, mjd@cs.auckland.ac.nz
• Tutor - Nan Huang, room 303-420, nhua630@aucklanduni.ac.nz (office hours: Tue & Wed 3-4pm)
• Tutor - Yan Kolezhitskiy, no office, ykol002@aucklanduni.ac.nz
• Class Rep -  Ganan Jeyakumar, gjey973@aucklanduni.ac.nz

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) and string matching algorithms (including Knuth-Morris Pratt and Boyer-Moore)
• 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)

Textbook

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]

Lecture Schedule and Recordings

Below are approximate weekly lecture topics with reference to the relevant textbook sections.

1. Review of prerequisite mathematics and data structures (Appendices D & E); first examples of algorithm analysis (1.1); asymptotics (1.3).
2. Running time of algorithms (1.2, 1.4. 1.6) NOTE: David Welch will be filling in for Mark Wilson this week.
3. Basic sorting algorithms (Chapter 2).
4. Advanced sorting algorithms (Chapter 2).
5. Efficient Searching (Chapter 3).
6. Graph abstract data type (Chapter 4).  [David's part starts]
7. Graph traversals (Chapter 5).
8. Basic graph applications (Chapter 5).
9. Weighted digraphs (Chapter 6) [Michael's part starts]
10. Graph optimization problems (Chapter 6)
11. Formal languages and text processing (Secs 7.1-7.5 of [DGW] or Sec 5.4 of [SW])
12. String matching algorithms (Sec 7.7 of [DGW] or Sec 5.3 of [SW])

All lectures to be recorded.  There 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 220 > 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 (3 @ 9% each)
• 3% tutorial quizzes (10 @ 0.3% each)
• 10% 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, and personalized/different for each student).
• The test (held in usual lecture room on Sept 12th) will cover the material of the first five weeks.
• You need to physically attend a tutorial to take the tutorial quizzes.
• All COMPSCI undergraduate courses have a separate pass requirement, i.e., you will need to pass both the test+exam and the assignments+quizzes components 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

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

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