DCS-128 Algorithms and Data Structures 2005

Aims and objectives ·  Lectures  ·  Local notes and resources  ·  Worldwide notes and resources  · 
Lab exercises  ·  Code used for examples  ·  Discussion

Although this page is old material, not directly used for teaching since 2005, read the last paragraph below in this section for why it might still be of some value.

This page archives the material for the course DCS128 "Algorithms and Data Structures" as it was taught in the academic year 2004/5. The tense on this page and direct addressing to students as "you" have been changed to represent the fact that this is now archive material rather than material intended for students currently taking the course. The course was in fact taught under the DCS128 code for one more year, but with extensively revised notes which became the basis for the new course DCS210 Algorithms and Data Structures in an Object-Oriented Framework. The web page for the 2005/6 version of DCS128 can be found here. The change reflected my feeling that further coverage of the object-oriented features of Java, including the then newly introduced generics, leading to an understanding of Java's Collections Framework, was needed, at the cost of dropping some of the content of the traditional algorithms and data structures course.

So what you see in the notes accessible from this web page is a fairly traditional algorithms and data structures course, not very different from how the subject would have been approached using programming languages which are structured but not object-oriented. It uses Java, but with its object oriented features used only where they are a necessary part of the implementation.

One of the biggest differences between the way DCS210 teaches this material and the way DCS128 taught it is the emphasis on generic algorithms and data structures in DCS210. In DCS128 we tended to look at collections of integers, with the idea that this could be generalised by replacing the int type for the content by some other type to build a collection of objects of that type. Before the introduction of full generic typing in Java using type variables, the only way to write generic collections was to use Object as the content type. You then had to use type casting when you retrieved elements from a generic collection in order to use them as their correct type. There was also nothing to make sure all elements in a generic collection were of the same type.

Java 1.5 (renamed as just Java 5) introduced generic typing with type variables into Java. It was the biggest change in the language since it was introduced, since it affected programming in Java at all levels. Other changes in Java before and since were on more specialist areas which would have little effect on what needs to be taught to a novice programmer just learning to program and using Java to do that. Although the extra syntax is an extra complexity that has to be learnt, once grasped it makes the use of types in Java far more coherent than it was before, which is why I as soon as I saw it and learnt how to use it, I felt that Java had to be taught from the start with its use of generic types as fundamental not introduced later as an "advanced" feature. It was obvious to me that the pre-generics practice of having types, but then throwing them all away when you used generic collections where everything was viewed as just Object, was silly. Realising this was the main thing that led me to redesign the course into something different from the traditional "algorithms and data structures" course I had taught up till then, which was not much different from the course I took on this topic in my first degree in the 1970s.

However, the old approach is not completely without value. In particular, if you are confused by the additional syntax and complexity which comes from polymorphism and generics, you may find some of the other topics easier to grasp when these aspects are not present in the notes and examples.


Lectures, these web-notes and overall design of the course by Matthew Huntbach.

Aims and Objectives

The aims and objective of the course are given here.

In summary, this was a course on algorithms and data structures which used the Java language to give executable implementation of the concepts discussed.

History and curriculum

2005 was the fourth year the course was taught. Only minimal changes to the curriculum were made since it was first taught in 2002. The course assumed students had basic experience with the procedural programming aspects of Java covered in their first semester course Procedural Programming. The course made use of the object-oriented aspects of Java were introduced to in the course Object Oriented Programming, which they took alongside this Algorithms and Data Structures course.

The previous year's web page for the course can be found here.


Marks for the course was divided between the final exam in May and two term-time tests. The final exam counted for 70% of the total marks, the term-time tests counted for 15% each.

The first test for 2005 took place on Monday 21st February. You can find a copy of the test paper here.

The second test for 2005 took place on Monday 4th April. You can find a copy of the test paper here. Model answers can be found here. A table giving the marks obtained by each student and some discussion of the results of the test, including analysis of common errors, can be found here.

College regulations regarding assessment, progression and resit entitlement can be found here. The first 32 pages of this PDF document are the relevant ones (the remainder is special regulations for qualifications other than the ones you are taking). Please note particularly the section on page 8 on attendance.

The two term-time tests set in 2004 can be found here and here, together with comments on how well they were done, and answers.

In 2003 only one term-time test was set, you can find a copy here. In 2002 two term-time tests were set, you can find them here and here.

You can find a copy of the May exam paper for 2004 here, 2003 here and for 2002 here.

Programming Language

The course used Java though avoiding detailed use of its extensive code library. I maintain a set of links on Java and programming in general, aimed at students who are just starting out to learn programming in Java. It is available here.


Students were encouraged to run Java under the Linux operating system.   In line with the aim in this course of concentrating on the basics, the course did not use a Java "Interactive Development Environment".

Local notes and resources

Notes written by myself can be found here. These were used rather than printed handouts. Code used in these notes can be downloaded from here.

Worldwide notes and resources

If any other web sites anywhere catch my eye as something that might be useful or interesting for you in the context of this course, I'll add them to a general links page, available here.

Lab Organisation

Lab sheets issued, along with solutions, were made available here. Code needed for the lab exercises could be downloaded from here.

Labs were in the Informatics Teaching Laboratory on Monday afternoons. Allocated lab times depended on the first letter of students' surnames:

A-D: 4-5pm
E-M: 3-4pm
N-Z: 2-3pm

It was expected students would spend more than one hour a week on lab work. The lab slots were only given to ensure everyone has a chance to access a machine. Students coiuld use a machine in the supervised lab space during the 2-5 lab period but outside their allocated lab time provided no-one whose lab time it needed it. Students could use the lab during unallocated hours (it is open early mornings, evenings and weekends), or they could use their own computer if they had one. During the lab hours, machines in the supervised lab space could only be used for Algorithms and Data Structures work, students using them for any other purpose could be asked to leave.

Students were expected to attend labs during your allocated time, and a register could be taken. Any student who is consistently absent from labs could be barred from the course.


This was a semester 2 course. Lectures were at 11am on Mondays in the Chemistry Lecture Theatre, 9am on Tuesdays in the Drapers Lecture Theatre (Geography Building) and 3pm on Tuesdays in the Chemistry Lecture Theatre. A summary of each week's lectures was posted here.

Discussion Group

There was a discussion group for this course which was used to give news about it and also as a place for public discussion about it. It can be found here. If students had a question, they could consider sending it to this discussion group (though I was happy to answer emails sent to me personally about the course), as there were probably many others with the same question, and all would be helped by a public discussion of it.


There were many textbooks suitable for further reading on the material of this course. Some of them are listed below. The problem is that most of these textbooks tended to assume more familiarity with Java programming than students would have at the start of this course, and to try and cram in more material than we could cover. In my experience this tended to make them a little intimidating for all but the most programming confident student.

You will also find complete on-line textbooks in the Worldwide notes and resources section of this website.

Matthew Huntbach
Last modified: 16 February 2011