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 and process data efficiently and how to assess how well your program scales when it needs to handle more data and users.

A course such as this one is a standard part of CS degrees worldwide, with good reason. The material is fundamentally important in many areas of computer science.

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? How do we get out of a maze efficiently?
• String matching is the task of finding efficiently a substring or subsequence in a text of characters. These string matching algorithms are widely used in text editors, bioinformatics, signal processing, computer security, and many more applications. Approximate or fuzzy string searching is also of interest for important areas such as data mining and image recognition.

The key learning outcomes for this course are as follows. Note that these are minimal expectations and that excellence requires practice!

• 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 constrast 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; optimization problems (e.g. shortest paths, minimum spanning trees).
• Can implement a few well-known fast string matching algorithms such as Knuth-Morris Pratt and Boyer-Moore.

• See Canvas page for assessment, course materials, lectures and tutorials.
• The standard textbook for the course is freely available: Introduction to Algorithms, Data Structures and Formal Languages by M. J. Dinneen, G. Gimel'farb and M. C. Wilson. The course follows the textbook closely.

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. Don't suffer in silence.

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