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

Welcome to COMPSCI 220 (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 was a modified merge sort, not a bubble sort selected as the Python's default sorting algorithm? How does your iPod find that song so quickly?
• 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?

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

• Lectures: See lecture page for schedule. Lecture notes will be available from this website or from Cecil. Lecture recordings will also appear on Cecil (this may take a few days, however).
• 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. It is placed in the Resource section of the course page.
• Tutorial: There will be a weekly tutorial. Please sign up on Student Services Online.

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

COMPSCI 220 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 COMPSCI 220, 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: 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 are the most important level, and in our case the foundations are the definitions. It helps to understand and learn definitions thoroughly. A good way to do this is to try and figure out at least three examples for every abstract concept.

Catching up on missed lectures and tutorials

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.