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

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.

Staff

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.

Assessment

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.

Systems

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.

Lectures

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.

Books

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: 20 January 2009