Algorithms and Data Structures: COMPSCI 220 Semester 2, City Campus

Welcome to COMPSCI.220SC (Algorithms and Data Structures). This course extends the algorithm and data structure material taught at Stage 1, and examines practical and theoretical aspects of program performance.

You will learn how to store, find, and handle data efficiently and how to assess how well your program scales when it needs to handle more data and users. No wonder courses such as this one are a standard part of CS degrees worldwide: The material is fundamentally important in many areas of computer science, and generations of computer scientists use it to give their work the cutting edge!

The core material includes topics from three areas. Here is a description with some typical questions from each area.

• Knowing what Data Structures to use is an essential part for creating efficiently algorithms that process data. How can we store data so we can find it quickly when it is needed?
• Algorithm analysis shows us how to get things done correctly and efficiently -- a good algorithm can make the difference between a program being a hog and it being usable in practice. You will learn how to analyse an algorithm for efficiency. In doing so, we encounter some classic algorithms that today are found everywhere in computing. We'll discuss questions such as: Why does the Java library not use bubblesort? How does your iPod find that song so quickly? Why is Java's HashSet potentially dangerous to use?
• Graphs are natural structures with hugely many applications, and we show you 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? How do we get out of a maze efficiently?

• Lectures: there will be 11 weeks of lectures - the course starts in week 2. Lecture notes will be available from this website.
• Textbook (mandatory): Introduction to Algorithms, Data Structures and Formal Languages (2nd Edition) by M. J. Dinneen, G. Gimel'farb and M. C. Wilson (Pearson NZ, 2009). The course follows the textbook closely. Ensure that you have a copy of this textbook and bring it to lectures.
• Tutorial: There will be a weekly tutorial. Please sign up on Student Services Online.

• 24% written/programming assignments (4 assignments),
  Due dates: 8:30 pm on Sunday 7 Aug, Sunday 28 Aug, Wednesday 5 Oct and Wednesday 12 Oct.
• 13% Written test, in lecture time on Friday, 16 Sep.
• 3% for PeerWise, see http://peerwise.cs.auckland.ac.nz/
  Marks awarded if students contribute 2 good questions each and answer/comment on 10. The PeerWise indicator of effort will be mapped to marks on the scale of 0-3.
• 60% written examination. Tests and exams are closed-book.
• We assume that you are already familiar with the academic honesty information and policy.

Seeking Assistance

For assistance with course material and course work you can visit or e-mail us, or ask the specialized demonstrator in the lab. The Department of Computer Science also has a team of support staff (see the posters around the labs for support contacts) who are happy to provide guidance on more general issues to do with your study in computer science.

How to get the best out of this course

COMPSCI220 is a part of the "theoretical computer science" spectrum and is a little more mathematical than the stage 1 courses in our department. That's nothing to be feared, though: Having a well-founded theory simply takes the guess-work and experimentation out of figuring out why something does (or doesn't) work. As they say: "Nothing is more practical than a good theory".

One tool that we will use frequently, though, is mathematics, albeit at a very low-key level. In preparation for COMPSCI220, please review the material on our "maths checklist", which we expect students to be familiar with.

This doesn't take long to grasp but makes life a lot easier when it comes to reading and understanding formulas!

Hint: It helps to understand and learn definitions thoroughly. A good way to do this is to figure out at least three examples for every abstract concept. Think of knowledge as a building. We need to build each level of the building well, or the floors above will fall down under pressure. The foundations (the definitions) are the most important level.

Catching up on missed lectures and labs

If you miss a lecture, catch up as soon as possible by reading the corresponding sections of the textbook. Ask classmates and/or the lecturer whether any extra material was covered. If you miss the deadline for an assignment and have a valid reason, contact the lecturer who set the assignment. If you miss the test/exam for any valid reason, or you sit the test/exam but believe that your performance was impaired for some reason, then you may be able to apply for an aegrotat, compassionate or special pass consideration.

Contacts

For specific questions about lecture material, contact the lecturer who taught it. For specific questions about the tutorials, contact the tutor. For specific questions about assignment marking, contact the marker and copy your email to the tutor.

The course coordinator is Ulrich Speidel. Feel free to contact me with general questions or any concerns you may have and that cannot be resolved by talking to the appropriate person.
[ Email: ulrich@cs.auckland.ac.nz, Office: Room 491 during city office hours, Extension: 85282 at Tamaki.]