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.
In summary, this was a course on algorithms and data structures which used the Java language to give executable implementation of the concepts discussed.
The previous year's web page for the course can be found here.
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.
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.
You will also find complete on-line textbooks in the Worldwide notes and resources section of this website.