Algorithms and Data Structures in an Object-Oriented Framework (“ADSOOF”)

ADSOOF

The module Algorithms and Data Structures in an Object Oriented Framework, abbreviated to “ADSOOF”, was originally developed in 2007 and taught until 2017. It was a 2nd year module, which followed on directly from the 1st year modules that introduced programming using Java.

ADSOOF used the Java programming language to introduce aspects of algorithms and data structures. It mixed this with with coverage of basic aspects of object-oriented programming. ADSOOF was started when an important developments of Java took place: the introduction of generic programming using type variables. This was in Java version 1.5, which later became called Java 5.

One of the reasons for bringing in the new module ADSOOF was that up till then algorithms and data structures had been taught in a way that ignored the fact that modern programming languages provide built-in code for all the standard algorithms and data structures that would be taught in introductory programming. For example, here is the previous module on algorithms and data structures that ADSOOF replaced.

In the old days, programmers really would have to write that sort of code themselves, but by 2007 it no longer made sense to teach it in that way. Instead, it was important to make clear from the start that in normal programming you could, and should, make use of the built-in code provided in standard programming languages. So Java's Collections code needed to be covered. However, in order to make proper use of this built-in code, it is important to have a good understanding of aspects of object-oriented programming that in practice many novice programmers find difficult to properly understand.

It is still important for skilled programmers to have a good understanding of how the built-in collections code works underneath. This helps ensure good use is made of it. For example, Java's classes ArrayList<E> and LinkedList<E> appear to work exactly the same in what they do. However, if you know how they are implemented, you would know that in some cases one is the most efficient to use, and in other cases the other is the most efficient. Also, learning how Java's built-in code for collections works, and practicing by writing basic algorithms and data structures code yourself, helps you develop general programming skills.

For example, there is no real need for you to write actual sorting algorithm code yourself when built-in sort methods are a standard aspect of modern programming languages. However, seeing how sorting algorithms are actually represented by code is a good way to learn the sort of programming you would need to be able to use when writing more advanced code for more complex algorithms that aren't provided as standard library code. It is also important to fully understand the principle of generalisation that the built-in code uses. There is no need for separate sorting methods to sort collections of different content types, instead generalised code makes use of Comparator objects or the compareTo method.

Similarly, there is no need to make direct use of cells-and-pointers code, instead just make use of built-in classes like LinkedList which are implemented in that way. However, understanding how cells-and-pointers code actually works, and being able to write you own code of that, helps you to get a clear understanding of the basic principle of how object-oriented programming works: variables refer to objects, and objects are entities which contain further variables that may refer to further objects or may link back to form loop structures.

ADSOOF Notes

The above was what ADSOOF covered: simple algorithms, with sorting algorithms as the main example, and data structures such as linked lists used to implement abstract data types. This led up to showing how the built-in code which in practice should be used for basic Java programming, is implemented.

Over the years, an extensive set of notes was built up to cover what was taught in ADSOOF, reaching the point where the notes were an equivalent to a full text-book. Links to these notes are now given below. These are the notes that were used for the 2016-17 version of the module. They have been slightly updated to make them available for general public use. Most of what is in them is still very relevant for modern Java, and for general aspects of algorithms and data structures used in combination with object oriented programming. However, it needs to be understood that since they were written, some additional features have been introduced in more recent forms of Java, and the notes will not be updated to include those.

Perhaps the most important basic aspect of modern Java that is not included in the notes is lambda expressions that were introduced in Java 8. These were introduced to allow Java programming to be done in a more functional language style. However, an important aspect of ADSOOF that was intended in part to give an introduction to a functional style of programming was “Lisp lists”. Java's standard collections types work in a mutable way, that is the methods called on collections change the actual collection they are called on. Functional programming, however, works with the concept of colletions being immutable, meaning that operations work by creating and returning new objects representing a change.

ADSOOF's Lisp lists were also introduced to give another example of the general concept of a concrete data structure implementing an abstract data type. Another reason for introducing the LispList abstract data type in ADSOOF was that it was a good way to give some simple examples of a recursive approach to programming. Being able to use recursion when it is appropriate is an important aspect of being a skilled programmer, but it is an aspect of programming that many seem to find difficult to pick up.

Sections

Each of the sections below represents what was approximately one week's teaching in ADSOOF: