Algorithms and Data Structures 2004: Lecture summary

This course will take a practical approach which extends what you have already done in the Procedural Programming course, and what you will be doing in the Object-Oriented programming course. This means that algorithms and data structures will be demonstrated using methods and classes written in the Java programming language, and an important part of the course will be doing exercises in the lab which involve writing and using Java programs. So although the main aim of the course is to give you familiarity with some of the concepts involved in the design and use of algorithms and data structures, illustrated by some commonly used algorithms and data structures, a subsidiary aim will be to give your more programming experience.

It is important to note that although Java will be the language used for illustration, the concepts involved are language independent. Algorithms can be described in English, or in some semi-formal notation that is part way between English and an executable programming language ("pseudocode"). The algorithm itself is the way of doing something, not any particular description of that way in some notation.

Since this is a course in understanding and developing algorithms and data structures, and not a course on the intricacies of Java, we shall not be making use of the large amount of code implementing common algorithms and data structures that exist in the code libraries that come with Java. Although in practice programmers would be advised to make use of them rather than re-build them, as computer scientists it's important that you know what happens underneath, and are confident in implemtning your own algorithms and data structures when the library associated with the programming language you are using does not already provide them.

The first thing we considered is that there are two fundamental ways of tackling the development of an algorithm. One is to use iteration. This means we start off with an initial state (i.e. a set of values) and find a way of repeatedly altering that state until it reaches a point where a solution is given. The other is to use recursion which means looking for a way in which the solution may be built up from a solution to a smaller version of the same problem.

We started off by considering a simple problem, the calculation of n^m, which is n multiplied by n multiplied by ... multiplied by n with a total of n repeated m times. Also, n¹ is just n while n⁰ is just 1.

An iterative way of dealing with this would be to start off with a state consisting of two variables, acc and count with acc initially set to 1 and count set to 0. Then repeatedly acc is multiplied by n and count is increased by 1 until count has the value m. Then acc will have the value n^m.

Iterative algorithms can be proved correct by means of the concept of a loop invariant. A loop invariant is some condition we know to be true at the start of the iteration, and which remains correct after each time the state is altered in the iteration. It remains true when the iteration has finished, and we know also at this point the condition for the iteration to finish must be true. From knowing these two things we can prove the final value of the state gives the solution. In the case of the iterative algorithm above to evaluate n^m, the loop invariant is that acc multiplied by n^m-count is equal to n^m. When iteration finishes, count must have the value m, so n^m-count has the value n⁰, equal to 1. So, given the loop invariant, when iteration finishes, acc must have a value equal to n^m.

A recursive way of dealing with the problem of evaluating n^m would be to note that if m is 0 the answer is 1, otherwise the answer is n multiplied by n^m-1. Evaluating n^m-1 is a smaller version of evaluating n^m so we can do it using recursion.

Recursion is described as "a method calling itself", which sometimes causes confusion. A better way of describing it is "a method calling another version of itself" which makes it clear that the arguments to the recursive call of the method are separate variables from the arguments of the original call of the method. The recursive call needs to be to a "smaller version" of the problem so that when it makes a recursive call and so on eventually there will be a call to the "base case" when no further recursion is required, in the example of evaluating n^m that is when m is 0 and the answer is 1.

Many people seem to find the concept of recursion difficult to grasp at first, and are anxious about exactly what happens when one call makes a recursive call to another call and so on. However, once you get used to it, it can often be an easy way to devise an algorithm. The best way to get used to it is just to assume the recursive call works without worrying about the details of how it works by making further calls and so on. This is also the basis of the way of proving recursive algorithms are correct, which is termed induction.

Induction involves assuming that the algorithm works for an arbitrary size of the problem, and if it does showing that it must also work for a bigger size of the problem. Then we prove it works for a small size of the problem (equivalent to the base case). From this we can deduce that it must work for the next size up problem, from this that it must work for the next size after that, and so on forever. If we show that our algorithm for working out n^m works when m is 0, and we show that if we assume it works when m equals k it must work when m is k+1 for any value of k, then since it works for m equal to 0 it works for m equal to 1, since it works for m equal to 1 it works for m equal to 2, and so on for all positive integer values of m.

The next thing we looked at involved thinking about the problem of evaluating n^m in a different way. The fundamental insight was that "n multiplied by n multiplied by ... multiplied by n" with n repeated m times is "n multiplied by n multiplied by ... multiplied by n" with with n repeated half of m times multiplied by itself. If m is odd, then round down the odd half, and multiply by an extra n, so for example n⁹ is n⁴ multiplied by itself multiplied by n since 4 is half of 9 rounded down to the nearest integer.

Again it can be seen that we are giving a solution to the problem in terms of the solution to a smaller sized version of the same problem, that is recursively. But this time, the size of the subproblem in terms of m is half the size of the original problem, not one less. To solve the problem half the size, we need the solution of the problem a quarter of the size and so on until we have the problem of size 1, which we can solve without further calculation since we know n¹ is n. Each time we make a recursive call we must do one or two multiplications, depending in whether the value of m is odd or even, so the total number of multiplications we have to do is at most twice the number of times we can divided the original m by two until we get 1.

We define the function log_b a (read as "logarithm of a to the base b") as the number of times a can be divided by b until it reaches 1. So it can be seen that with our new algorithm there are at most two times log₂ m multiplications needed to evaluate n^m. This compares with m-1 multiplications in our earlier algorithms. For large values of m this can make a huge difference. For example, for m having values of around a million, the logarithm to the base 2 is 20, so it can be seen that we would need to do at most 40 multiplications to evaluate n^m, rather than a million multiplications. This is a substantial imprivement in efficiency. Imagine if each multiplication took a milli-second (i.e. a thousandth of a second) to complete. In the first case this would result in us having to wait several minutes for the evaluation of n^m to complete, in the second case it would appear to us to complete almost instantly.

We also looked briefly at sorting, and one particular sorting algorithm called selection sort. We shall discuss sorting in more detail next week, and a lecture summary on the topic will be given then.

Code for the examples used this week can be found in the powers subdirectory of the code directory for the course. Please note that the Java files in this directory contain complete programs, that is they consist of a class with a method called main which takes an array of strings as its argument and has void as its return type. The main method is there just to provide a framework so that you can run the code. You do not need to be concerned with the code in the main method which uses things from Java's built-in library in order to be able to read data from the screen. Since this is not a course on Java's libraries, none of it is examinable, you do not have to learn it, and you can completely ignore it. The important thing in each of the files here is the method called power. In the different files you will see different versions of this method, the code in them is the same as the code which was shown in the slides in the lectures.

Notes covering the material of this week are given in The Powers Example.

Week 2: 19/20 January

Sorting means taking a collection of data and putting it in an order determined by some comparison test. So far the only way of collecting data you have seen is the array, so we discussed sorting arrays. For simplicity we considered sorting arrays of integers, with the comparison test being that one integer is less than another. It is important to be aware that the same algorithms could be used for other types of data, for example we could sort arrays of strings with the comparison test being whether one string comes before another alphabetically.

The first sorting algorithm we considered was selection sort. This involves repeatedly searching the portion of the array starting with the element indexed by an index integer i and ending with the last element of the array (which is indexed by a.length-1 if the array is referenced by a variable called a), to find the position of the lowest integer in that portion. This integer is then swapped in the array with the integer at the position indeed by i. It can be seen that if this is first done with i set to 0, then with i set to 1 up till i set to a.length-2, the whole array will be sorted.

Formally we can argue this with the following loop invariant:

"The array contains all the elements that were in it originally. The portion of the array up to but not including the element indexed by i contains the lowest i elements of the original array in numerical order".

It can be seen that this is true before the loop starts, since the array is then in its original state and with i set to 0 obviously the elements up to that indexed by i are sorted because there aren't any. It can be seen that this remains true each time the body of the loop has been executed and the update concluded, since the ith smallest element in the array is put in its position each time round the loop, and i increased by 1. So it must still be true when the loop finishes, that is when i is equal to a.length-1. Then the first a.length-1 elements of the original array must be in their correct place in the sorted array, and since the remaining element must be the highest one and is last in the array, it too is in its correct place.

The next algorithm we considered was merge sort. The basis behind this is that we split the array into two arrays, the first containing the front half of the original array, the second containing the back half. Then we sort each half, so we have two sorted arrays, which together contain all the elements of the original array. We can then put these elements back into the original array by taking one at a time from either array, keeping an index of each saying the point at which we have taken from each. This process is the "merging" of the two sorted halves.

Each half is itself sorted in the same way (not by some other sort algorithm like selection sort, as I have found in the past some students seem to believe). This is an example of recursion, and is the sort of thing some find mystifying. The reason why it works is that we are actually reducing the problem into two smaller versions of the same problem, and then since we use recursion into four even smaller versions of the same problem, and so on. Eventually, we will reduce the problem to the smallest possible size of the problem, which is sorting arrays of length 1, and then no more recursion is needed since an array of length 1 cannot be anything but sorted so no further work needs doing on it.

We noted that there are two ways sorting an array can be approached, and later we will see this with other data structures. One, termed destructive actually changes the contents of the array to put them in sorted order. The other, termed constructive, makes no changes to the original array, but instead creates a new array which has the contents of the old array copied into it but put into sorted order. A destructive method will have return type void, since it does not return anything but has its effect by changing the array passed as its parameter. It is destructive because it destroys the record we had of the original ordering of the array. We would use a constructive method where we wanted an sorted version of the array, but also wanted to keep a record of its previous unsorted order. A constructive method dealing with arrays of integers will have return type int[], indicating that it returns a new array of integers.

Next we looked at searching. I sometimes find students confuse searching with sorting. Searching just means finding whether a particular element is present in some collection of elements, so it would involve a method which takes the element as an argument and has return type boolean. A variation on this theme, when dealing with indexed data structures such as arrays, is to return the position of the element in the array. In this case, it needs to be decided what to return if the element being searched for is not in the array, commonly -1 is returned in these circumstances.

Note that a static search method will take the data structure it is searching in as another argument. You will see this may not be the case when we consider object methods, but at this point you have only seen static methods. Also, the issue of whether the method is constructive or destructive does not come up with searching, because searching does not involve making any changes to the data structure being searched.

If the array is unordered, then to find any particular element we have no choice but to look through the elements of the array one element at a time until we have either found the element we are looking for, or have looked at every element and not found it. If the elements in the array are stored in order, however, we can employ an algorithm called binary search. In binary search, we look first at the middle item of the array. If it is the item we are searching for, then we have found it. If the item we are searching for is less than this middle item, then we need only look for it in the portion of the array below the middle item. If the item we are searching for is greater than this middle item, then we need only look for it in the portion of the array above the middle item. It can be seen that we have a situation similar to that when we considered the more efficient algorithm for calculating n^m, that is one where we have a recursive call which cuts the size of the problem we are solving in half rather than reduces it by 1 element.

The big-O notation is a way of describing the efficiency of algorithms which utilises this way of thinking. If the size of the data to an algorithm is N, which could be the size of the array as in searching or sorting, or an integer parameter as in the powers example, then the efficiency of an algorithm can be described as O(f(N)) where f(N) is some function of N. The capital 'O' used here is why the notation has the name it has. Common functions used are N², N, log N and N log N (where the last of these means "N multiplied by the logarithm of N"). When speaking about it, we pronounce the capital 'O' as "order", so an algorithm which is O(N²) is also called "of order N squared". Algorithms of O(N²) are also called quadratic, algorithms of O(N) are also called linear, and algorithms of O(N³) are also called cubic.

In general, the function used in the big-O notation contain no constant multipliers, and no additions. This is because when considering efficiency only the most significant term of a sum is considered. For example, if we have aN²+bN+c, once the value of N becomes large, there is hardly any difference between this value and aN² so we might as well ignore the bN+c. The constant multiplier a can be ignored as well, since the time taken to execute the algorithm will have all sorts of constant multiplying factors which are not relevant to the algorithm itself, for example the speed of arithmetic operations on the computer it happens to So if we calculated that an algorithm on a piece of data of size N made approximately aN²+bN+c calculations to execute, we would describe it as O(N²).

A part of an algorithm where the amount of computation is not dependent on the size of the data has O(1). If an algorithm takes the form of a loop which runs through N one at a time, as in:

for(i=0; i<N; i++)
   dosomething

As we saw with the powers example, an algorithm which makes a recursive call on a size of the problem half that of the original makes a total of around log N calls for data of size N. So the algorithm is O(log N) if it does nothing else dependent on the size of N. It is of O(N log N) if on each recursive call it does other work dependent on the size of N which is of O(N). Note that a loop which cuts the size of the problem in half, as in:

for(i=N; i>1; i=i/2)
   dosomething

It can be seen from this, that selection sort with its loop within a loop is of O(N²). Merge sort does its merge work which involves going through all the data and makes recursive calls on half the size of the data, thus it is of O(N log N). Binary search is O(log N) because it does a fixed amount of computation on each recursive call, and the recursive calls halve the size of the problem.

The important thing is that the order of the algorithm dominates its efficiency, at least once we start dealing with large amounts of data. Thus, for example, finding an algorithm of O(N log N) to solve a problem will do far more to give us a quick solution than anything (even the speed of the computer it runs on) that makes an existing algorithm of O(N²) run faster but keeps it at that order.

Code for the examples used this week can be found in the sort and search subdirectories of the code directory.

Notes covering the material of this week are given in The Selection Sort Example, The Merge Sort Example and Comparing Sorting Algorithms.

Week 3: 26/27 January

It's important to note this means if one method calls another method which has an argument or local variable of the same name as one in the original method, they are not the same variable. Changing the value of the variable in the method that was called will have no effect on the value of the variable of the same name in the method that called it. This applies in recursive calls as in any other method call. A recursive call sets up a new environment which has the same variable names as the environment it was called from, but they are entirely separate variables.

We noted that assignment in Java for values of any types except the "primitive" types (i.e. numerical values, characters and booleans), involves aliasing. That means that if we execute b=a the result is that b is made to refer (or point) to the same value that a points to. The only non-primitive type we have seen so far (apart from Strings) is the array. The consequence of aliasing with arrays is that once we have executed b=a and before we change what a or b refer to by assigning either of them to something else, for any i the sub-variables a[i] and b[i] are the same thing. Changing a[i] by an assignment to it, for example a[i]=8 will cause b[i] to be assigned the same value, 8 in this case, since both are different names for exactly the same piece of memory in the computer.

Aliasing applies when arrays are passed as arguments to methods. If we call a method with an array argument, a new variable in the new environment is created to refer to that array. This variable is an alias of the variable in the old environment that refers to the array. So the effect is that there are two separate variables referring to one array unless at any stage in the execution of the method the array variable is made to refer to another array through an assignment. This aliasing is the reason why if a method call makes changes to the values in an array passed as an argument those changes persist when the method has finished executing and we have returned to the old environment.

We noted a special version of recursion called tail recursion. A method call is tail recursive if it is recursive (that is, is a call to the method in whose code it appears) and the value it returns is returned as the return value of the call that made it. The effect is that there is no computation in the original method call after the recursive call is made. As noted above, when we finish a call we execute the remaining code for the method that made the call in its old environment. However, if there is no more code to execute because the result of the call is returned as the result of the method that made the call, there was no need to have saved the old environment as it was never used.

In a tail recursive call, the new environment has the same variable names as the old environment. In fact, since the old environment is never going to be used again, we could just use the same variables as in the old environment rather than create a completely new set of variables. To achieve this, we would abandon the use of recursion and instead use a loop, replacing the recursive call by assigning to the variables that were the parameters of the recursive call the values that would have been passed to them in the recursive call. The condition to exit the loop is the condition to execute the base case in the recursive call, so the condition to stay in the loop (which is what is actually written as the test in a while or for loop) is the negation of this.

So, any algorithms that can be expressed using tail recursion can also be expressed using iteration. It is more efficient to use iteration, since that does not involve making space for new variables and giving them values. It therefore makes sense to try and reconfigure recursive algorithms to make them tail recursive. We showed an example using the "powers" computation we considered in week 1. We also noted that the binary search method given in week 2 was in fact tail recursive. Changing the recursive code given to iterative code in the way suggested leads to the code you saw in week 7 of the Procedural Programming course. Since recursive algorithms cannot always be made tail recursive, it isn't always possible to change them to iterative algorithms in this way, but it is always possible (though not usually useful) to perform the chnage in reverse order and turn an iterative algorithm into a tail recursive one.

We considered briefly the use of the array and count data structure to store a set of data that can be changed by adding or deleting items as a program executes. The issue here is that once we create an array in Java it is of fixed size. It would be inefficient to create a new array of a different size every time an item was added to or deleted from the set, copying all the other items into the new array. So instead we create an array of the maximum size we think we will ever need, and have a variable which at any point in the execution of the program holds a value giving the portion of the array that is in use at that point to store current data. Then to add an item to the set we simply put it in the part of the array one cell beyond the used portion and increase the count by one so that cell is included. To remove an item from the set, we would create a "hole" in the array where that item was stored, but we can cover that by copying the last item in the used portion of the array into that "hole" where the deleted data was, and reducing the count by one so the original copy of the last piece of data is no longer counted. This was a start on a new topic, the idea of abstract data types, which we shall cover in more detail next week. Abstract data types involve the use of objects, which by now you will have covered in the Object Oriented Programming course.

Notes covering the material of this week are given in The Array Search Examples, More Searching and Sorting Examples and Sets Using Arrays, Part 1.

Week 4: 2/3 February

The first version of the program had all the code in the main method, which was long and complex. We then broke the code up so there were separate methods add, delete and member to represent the operations possible on a set (and also a method called print to print out a text representation of one). However, this code still did not properly put together the array and count as a single entity representing a set. So we went further and put the array and count representing a set, together with the methods representing the set operations in a separate class. Then the class with the main method executed when the program starts contained only the code that interacts directly with the user (or the "front end" code) while all the code for representing and manipulating sets was in a separate class.

We made the array and count fields in this set class private so that no code in the "front end" class (or any other class) could access them. So the only way set objects could be manipulated was through the public methods add, delete and member, plus toString to provide a text representation of the set for printing, and the set object constructor which returned a new object representing the empty set. The consequence was that our code for the set maintenance program was broken up into two classes each with their separate roles and able to interact only in a limited way. This clear division of responsibility between pieces of code makes the program easier to understand and for it to be less likely that errors will arise due to unexpected interactions between different pieces of code.

This gave us the concept of an Abstract Data Type (or "ADT" for short). An ADT is viewed in terms of the operations possible on it, and not in terms of how it is actually stored on the computer. When using Java, an ADT is represented by a separate class, with the public methods in the class defining it. We showed how we could change the representation of sets inside the set class without having to make any changes to the front-end class which used the set class. We changed the representation of sets from an unordered array and count to an ordered array and count, which enabled us to write the member method in a way that used the efficient binary search rather than the inefficient linear search. A completely different way of representing sets of integers was as an array of booleans, where if a is the array, then a[i] is true if i is in the set, and false if it is not. We could change the set class in our program to use this completely different representation without having to make any changes to the "front-end" class (although a drawback to this representation is that it only works if the integers in the set can only come from a limited range).

So we have a data structure, that is a collection of variables which together represent some abstract concept such as a set, protected by being made private fields inside objects whose public methods represent the operations possible on the abstract concept. This is known as information hiding. This is a good idea, because the less separate pieces of code need to know about each other, the easier it is to fit them together and be sure they will work properly in combination.

Having previously seen the idea of constructive and destructive operations on data structures, we were able to consider the idea of constructive implementations of abstract data types, our examples until now having been destructive. The operations which change a set are add and delete and in our destructive implementation of sets these operations made changes to the array and count fields of the set object. The destructive methods had void as their return type since they had their effect by making changes to the object itself. In a constructive implementation, a new data structure representing the changed object is constructed, and a new object holding that new data structure is returned as the result of the method representing the operation. Meanwhile, the data structure in the original object is unchanged. In order to create the new object, the class for the constructive implementation of an abstract data type needs a private constructor which takes as its argument(s) the new data structure.

We noted that if an operation made no change to an object (for example, adding an element to a set when that element is already in the set), the constructive method called on the object could return a reference to the same object. In Java this is done through the keyword this. At any point in Java where a method call is made on an object, say obj.meth(...), when the code for the method meth(...) (which cannot be a static method) is executed, the word this in that code refers to the object obj.

Code for the examples used this week can be found in the sets directory of the code directory. The classes UseIntSets1 and UseIntSets2 show the set maintenance program implemented without a separate class for sets. All the other UseIntSets classes are just front ends, giving the user interface while the set implementation is in other classes. IntSet1 through to IntSet7 give the code covered this week.

Notes covering the material of this week are given in Sets Using Arrays, Part 2 and Sets Using Arrays, Part 3.

Week 5: 9/10 February

If obj1 and obj2 are two variables of a type given by a class for mutable objects, then the assignment obj2=obj1 is problematical, since it means that obj1 and obj2 both refer to the same object, and any change made through a method called on one of the variables will change the object referred to by the other. To avoid this, in classes for mutable objects it is a good idea to have a method which returns a copy of the object it is called on, by copying its data structure and constructing a new object to encapsulate the copy. Then in the place of the assignment we would call obj2=obj1.copy(). We saw how would could use inheritance to create a new class which added this copy method to an existing class. The new class needed the copy method, a private constructor in order to be able to pass the copy of the internal data structure to a constructor to build a new object around it, and a public constructor which just calls super() to use the public constructor of the class it inherits from. All other methods and the fields giving the data structure inside the object are not given as they are provided automatically through inheritance.

We looked at axioms which complete the concept of abstract data types. An abstract data type is defined in terms of the operations possible on it (in Java, given by the public methods of the class that implements the abstract data type) and by the way those operations interact. Axioms are rules that define how the operations interact, and are written assuming the operations are constructive. For example, the axiom:

 s.add(e).member(e) == true

We considered adding union and intersection operations to our set abstract data type to make it more like the concept of set used mathematically, for example in the Discrete Structures course you may be taking. We saw how the axioms for sets could be extended to provide axioms correctly describing how union and intersection should work. We added the operations as methods to a class which implemented sets constructively. So, for example, if s1, s2 and s3 are variables of the set type, s3=s1.union(s2) as a statement causes s3 to refer to a set object representing the union of the sets referred to by s1 and s2, while s1 and s2 themselves remain unchanged.

Our first attempt at a method for union was:

 public IntSet8 union(IntSet8 set)
 {
  for(int i=0; i<array.length; i++)
     set=set.add(array[i]);
  return set;
 }

We noted that it was possible in the code implementing the call s1.union(s2) to refer to the array field of s2 as well as s1. This is because although that field is declared as private, s2 is of the same class as s1. In general, it is possible to access the private fields of objects passed as arguments to methods if the methods are in the same class as the object argument. Given the call s1.union(s2) and the method heading public IntSet8 union(IntSet8 set) in the code for the method union, set.array refers to the array field of the s2 object, while array on its own refers to the array field of the s1 object. It is also possible, and perhaps advisable for clarity, to refer to the array field of the s1 object as this.array.

Given this, a more efficient implementation of union directly accessed the array fields of both set objects. If the implementation of set is with an ordered array, the code to create the array representing the union of two sets is very similar to the code for merging two ordered arrays used in merge sort. However, it needs to copy in just once any element that occurs in both arrays. As this is not known in advance, a temporary array to hold the merger is set to sum of the sizes of the two arrays being merged, but this will not be fully filled if there are any duplicates. A smaller array of the size necessary to hold the merger less the duplicates is created and encapsulated in the new object returned to represent the union.

In order to illustrate the general principles of abstract data types, we looked at another one, the sequence to see how using it involved similar techniques to those we have developed to implement sets. The sequence abstract data type has the concept of a list, that is a collection where the order of the elements in the collection is important. It also has the concept of an "insertion point". In a sequence, the "delete" operation deletes the element at the position of the insertion point, while the "add" operation adds a new element just before the insertion point. There are also operations to move the insertion point forwards and backwards in the collection.

The code covered in the lectures this week is in the classes IntSet7 through to IntSet10 in the sets subdirectory of the code directory, and also in the class IntSequence in the sequences subdirectory (with the front-end for the sequence manipulation program in the class UseIntSequences).

Notes covering the material of this week are given in Sets Using Arrays, Part 4.

Week 6: 16/17 February

In the second lecture we covered the topic of linked lists.

A linked list is the simplest example of a recursive data structure. It involves an object (termed a "cell") which has one field of the same type as the object. So this field may be set to refer to another cell, which has a field referring to another cell, and so on. Thus we have a list of cells linked together, each of which holds some data (in our examples, just a single integer) as well as the link to the next cell. The list does not go on for ever because any object field may be set to the special value null meaning "unset" or "does not refer to any object".

Operations on a linked list often involve a pointer (which is just a variable of the same type as the cells of the linked list) which is initially set to refer to the first cell of the linked list, but is then repeatedly altered to refer to the next cell of the list, so it moves down the list. For example, to test whether a particular integer is found in a linked list of integers, we set a pointer to refer to the first cell of the list. Then we have a loop whose update statement changes the pointer to point to the next cell in the list, and whose test statement tests that the pointer is not equal to null and it does not point to a cell whose integer is the integer we are searching for. If the loop finishes because the pointer has become equal to null then we know we have gone through the whole list and not found the integers we are searching for so it cannot be there. Otherwise, the loop can only have been exited because the pointer points to a cell that contains that integer.

Deleting an integer from a linked list of integers involves moving a pointer to point to the cell before the one holding the integer to be deleted. Then the link to the next cell of the cell the pointer is pointing to is set to refer to the link to the next cell of the cell it is pointing to. This has the result of cutting out from the list the cell with the integer we want to delete. Note that if the cell is left with nothing pointing to it, as with any other object which nothing points to, it can be assumed to "disappear", in practice allowing the computer store it used to be re-used when a new object is created. This is referred to as garbage collection.

A linked list is a data structure, not an abstract data type. This is because the fields in cells are not declared as private and they may be accessed and changed through assignment by code in other objects. Compare this with an abstract data type, which is represented by an object whose fields are private and which can only be accessed by its public methods.

We had been considering over the previous three weeks various ways of implementing the abstract data type Set. We had an object representing a set, which was an abstract data type as the only way it could be accessed is through its public methods add, delete and member, which matched the operations of a set. The set had private fields giving a data structure. representing the abstract data type. The methods either changed the data structure (for a destructive implementation) or created a new data structure and put it inside a new object (for a constructive implementation). Now we saw that linked lists were yet another data structure that could be put inside an object to represent sets. It is the same abstract data type Set as previously, because its public methods seem to behave in exactly the same way, and a program using a set object implemented with a linked list would observe nothing different from one using a set object implemented with an array.

The implementation of a set using a linked list showed an example of a nested class. The code for a nested class is written inside another class rather than in a separate file of its own. The reason for doing this is to show that the nested class exists only to give us the data structure to go inside objects of the enclosing class, and cannot be accessed outside that class. So our set class had a cell class as a nested class inside it. The methods in the set class which manipulated the linked list are said to treat it as a global linked list, because the list is just assumed to be there rather than passed in as an argument. This can be done because the methods are called on a set object which has a linked list field, and so when a method is called the "global" linked list it refers to is the linked list of the set object the method call was made on.

The code covered in the lecture this week is in the class IntSet11 in the sets subdirectory of the code directory.

Notes covering the material of this week are given in Sets Using Linked Lists.

Week 7: 23/24 February

When dealing with operations on the linked list field inside an object representing a set, we found we had to have an initial public method representing the operation, which called a private static method to do most of the work. The reason for this is that our public method took as its argument only the integer to be added or deleted. Since the method is attached to a set object, and the set object has a single field which is the linked list, then this linked list can be referred to by the name of the linked list field in the code for this public method. But the private method needed to take both an integer argument and a linked list argument since its recursive calls needed to be able to refer to subsections of the list rather than the list as a whole. This auxiliary method might as well be static since it makes no reference to the list field of the set object.

To delete an integer from a linked list destructively, if the integer is in the first cell of the list, then the list is replaced by its next field. This special case is dealt with in the initial method. Deleting anything but the first cell is dealt with in the private recursive method. To delete an integer from an empty list, leave the list unchanged. To delete an integer from a linked list where the integer is in the second cell, alter the next field of the first cell to become equal to the next field of the second cell, thus cutting out the second cell. Otherwise, delete the integer from the rest of the list (using recursion).

To add an integer to a linked list, if the linked list is null, replace it by a reference to a cell whose first field holds the integer and whose next field is empty. This is the special case dealt with in the public method. Otherwise, to add an integer to a linked list without creating duplicates, leave the list unchanged if the integer is in the first cell of the list. If the first cell of the list holds a different integer and its next field is null, set its next field to a new cell whose first field is the integer to be added and whose next field is null. Otherwise add the integer to the linked list given by the next field of the first cell (using recursion).

In both cases, note there is a complication caused by the need for special handling of the first item in the list. Otherwise, addition or deletion of items in the list is achieved by changing the pointer of the cell before the cell to be added or deleted.

We noted that constructive forms of the operations were easier to write recursively, but harder to write iteratively. For example, to copy a linked list constructively, if the linked list is null the copy is null, otherwise the copy is a new cell whose first field is the item in the first field of the linked list being copied, and whose next field is a copy of the next field of the linked list being copied. This simple recurisve description translates almost directly into Java code. An iterative algorithm for copying linked lists was given, but it was more complicated.

As with our constructive implementation using arrays, the constructive implementation using linked lists needed to have a private constructor which took as its argument the modified data structure representing the change (new linked list in this case) and constructed an object to encapsulate it.

As a side issue, we looked at string tokenizers. Although strictly they are not part of the course, as the course is not about the classes and methods built into Java as part of its library, they were seen in the code used to read a representation of a list from the screen and convert it to a linked list data structure. They are related to the concept of an enumerator which we shall see later in the course. The class StringTokenizer is in the package in the Java library called java.util so at the top of any file that uses it the import statement import java.util.*; must appear. Import statements are the only thing in Java which occurs outside classes.

The constructor which creates a new StringTokenizer object takes a string as its argument. Then, each time the method nextToken() is called on the object, it returns the next word from the string, treating blank characters as word separators. There is a constructor for StringTokenezer which enables you to specify what characters you wish to use as separators, we needed to use this form so we could treat commas as separators. The other method used on StringTokenixer objects is hasMoreTokens() which returns true when it has not gone through all the words the string breaks down into, and then false when it has.

The code covered in the lectures this week is in the classes IntSet11a, IntSet11b, IntSet12, IntSet14, IntSet17 and IntSet19 in the sets subdirectory of the code directory.

Notes covering the material of this week are given in More Destructive Set Implementations and More Constructive Set Implementations.

Week 8: 1/2 March

If there is a possibility of a linked list argument being circular, it is necessary to modify code to allow for it and stop the recursion or iteration if it returns to a previous section of the linked list. This could be done by keeping a count of the depth of recursion or the number of links the pointer has been moved. If another pointer is run down the linked list one less than this count and encounters a cell which is the same as the one currently being handled, we know we are in a circular list and have returned to a previous section. Remember two pointers ptr1 and ptr2 point to the same cell if ptr1==ptr2 is true. Doing a check for pointing to the same cell is the only time the equality check == is used with anything apart from numerical and character data, since even if the cells ptr1 and ptr2 point to contain the same data, ptr1==ptr2 will still be false if they are different cells.

The issue of circular lists does not apply to our use of linked lists as a data structure kept privately internal to set objects. When this is done, the linked list can only be accessed and altered by the public methods of the object. As these are guaranteed not to produce circular lists, there is no need to take account of the possibility. This shows a benefit of encapsulating data structures within objects representing abstract data types - we can guarantee that anomalous conditions cannot hold, so we don't have to put checks for them in the code.

Most of the lecture time in week 8, however, was given over to binary trees. A binary tree is a data structure made up of cells which have two recursive fields. So a tree is either empty (represented by null) or consists of an item of data and two further trees. The data is referred to as the root, the two further trees are referred to as the left branch and right branch.

Binary trees may be used for various applications, but a common one is to store data which has an order in which case the binary tree needs to have the property of being ordered. A binary tree is ordered if every piece of data in its left branch is less than the root, every piece of data in the right branch is greater than the root, and the left branch and right branch are similarly ordered (it is, of course, also ordered if it is null).

Given an ordered binary tree, if we want to test whether a particular piece of data is stored in the tree (in other words, do a search), we first look at the root. If the root item is the piece of data we are looking for, we know it is stored in the tree and can return true (actually, we first check if the tree is null, in which case we know the data isn't in the tree and return false). Otherwise if the piece of data we are looking for is less than the root item, we confine our search to the left branch, otherwise we confine our search to the right branch. If the branches are of approximately equal size, this means we cut our problem of seaching to one of half the size, and we know that an algorithm which repeatedly does one operation and then cuts the problem to half the size is O(log N). Compare this to searching for an item in a linked list, where even if it is ordered on average we have to go through half the list one item at a time, making the search O(N).

Unfortunately, the O(log N) search property is spoilt if we cannot guarantee that the tree is balanced (that is, that at any cell in the tree, the left and right branches of the cell will contain approximately equal numbers of cells). There are variations on the ordered tree data structure with algorithms with algorithms for inserting and deleting items which not only keep the tree ordered, but also keep it balanced. However, these are beyond the scope of this course, so we looked only at simple insertion and deletion algorithms.

We looked at an iterative destructive algorithm for adding a new item to an ordered tree and keeping the tree ordered. This involved starting with a pointer at the root, and moving it down the left or right branch depending on whether the item being inserted is less than or greater than the root. When the pointer is pointing to a cell where its next move would be to a branch that is null, that branch is replaced by a cell which contains the item to be added as its root, and has null as its left and right branches. Note, as with linked lists, to change a structure destructively it is necessary to do it via a pointer to a cell which contains the field to be changed.

Deleting an item from an ordered tree works similarly if the item to be deleted is in a leaf cell (that is, one whose left and right branches are both null). In this case we can replace the link to that cell in the cell above it in the tree by null. If the item to be deleted is in a cell one of whose branches is null we can replace the link to that cell in the cell above it by a link to its other branch. So the algorithm for deletion, as with addition, works by starting at the root and moving a pointer to the left or right as appropriate until it points to the cell above the one which contains the data item to be deleted. The problem comes when the cell containing the data item to be deleted has neither an empty left branch nor an empty right branch.

To delete an item which is in a cell with a non-empty left and a non-empty right branch, we have to replace that item with the rightmost item of the left branch, and cut out that rightmost cell. To do this, we set a pointer to the root of the left branch, then continue moving it to the right until it points to a cell whose right branch points to a cell whose right branch is null. Setting the right branch of the cell to which the pointer refers to the left branch of the cell ito which the the right branch refers will cut off the rightmost cell. Note again, the algorithm is made a little more complex by the fact that to change the tree destructively we need to do so through a pointer to the cell above the one being deleted.

The reason why to delete a cell in the middle of a tree we have to replace it by the rightmost cell of the left branch is that this will keep the ordered property. The rightmost cell of the left branch must contain the largest item in the left branch which is still smaller than everything in the right branch. Therefore putting it at the root means that everything in its left branch will be smaller than it, and everything in the right branch greater than it.

We also considered constructive changes to binary trees. This means creating a new binary tree which represents the change, while keeping the old tree unchanged. We did this using recursion. To make a new tree representing a change to the left branch of a tree, we make a new cell whose root is the same as the root of the tree being changed, whose right branch is the same tree as the right branch of the tree being changed, and whose left branch is created by applying the change operation recursively to the left branch of the original tree. Similar applies when creating a tree representing a change to the right branch. Note the result of doing this is that the cells in the unchanged branch of the tree are shared by the original tree and the new tree. This is not a problem so long as we can guarantee all our changes will be constructive.

We considered tree traversals which means going over all the cells in the tree. This would be done, for example, if we wanted a string representing of a set stored in a tree. To go over all the cells in the tree we need to do three things: go over the root cell, go over all the things in the left branch, go over all the things in the right branch. The last two of these things are recursive (and the base case is when the tree is null in which case there are no cells to go over). If we process the root before the branches, it's referred to as pre-order, if we process the root between processing the branches, it's referred to as in-order, if we process the root after the branches it's referred to as post-order. In-order traversal of an ordered binary tree means we process the items in the tree in order, so from lowest integer in numerical order to highest in an ordered tree of integers.

Breadth-first traversal means processing the root of the tree, then the items at depth one in the tree, then the items at depth two, then the items at depth three, and so on. We noted this could not be done using a simple recursive technique, since it means jumping from the left branch to the right branch and then back again. A technique for traversing a tree breadth first will be shown later in the course.

The code covered in the lectures this week is in the classes IntSet13, IntSet16 and IntSet18.

Notes covering the material of this week are given in Sets Using Trees, More Destructive Set Implementations and More Constructive Set Implementations.

Week 9: 8/9 March

The abstract data type List has a method cons which takes an integer argument (assuming we are dealing with lists of integers) and returns a List object representing the list the method was called on with the integer argument added to the front. It also has a method isEmpty which returns a boolean value, true if it is called on a List object representing an empty list, false otherwise. The method cons replaces the direct use of the constructor for cells in the linked list data structure. Note that with linked lists, the empty list is represented by null, which is not an object so no method can be called on it. However, with the abstract data type List, the empty list is represented by an object. A method is needed to produce a new object representing an empty list, but this has to be a static method since it isn't called attached to any object. As a static method, when it is called it must be attached to the class name, so List.empty() returns a new object representing the empty list.

The abstract data type Tree has methods left, right and item replacing the direct access to the fields of the same names in the linked tree data structure. It also has method isEmpty and static method empty for testing for and creating a new empty tree, analogous to the methods of the same name in the abstract data type List. The equivalent to List's cons for trees is a method called make, however make is a static method while cons is not. The reason for this is that while it makes sense for cons to be called on a List object, so for example list.cons(n) returns a new List object representing the list where n is added to the list represented by list, it doesn't make sense for make to be called on a single Tree object, since its effect is to take two trees and a data item and make a new tree. So the call Tree.make(n,t1,t2) returns a new Tree object with root value n, whose left branch is the Tree object represented by t1 and whose right branch is the Tree object represented by t2.

Objects of type List and type Tree are immutable. They do not have any methods that can be called on them which actually change the object, only methods which return a new object. So, for example, the call list.cons(3) does not change the object referred to by variable list, and it makes no sense to use it as a statement on its own as that has no effect (it does not cause list to be changed to "add 3 to the front of it"). It only makes sense to use it where a List object is required since its effect is to return a new List object representing the list referred to by list with 3 added to the front. It is possible to write the statement list=list.cons(3), but important to note that even this does not represent a destructive change. Rather, it represents the variable list being made to refer to the new object, the object it used to refer to is not itself changed. So if list=list.cons(3) is executed, if anything else refers to the object list used to refer to before the execution of the statement, it still refers to it afterwards and still represents exactly the same list it represented before, only list has been changed to refer to a new object reprseting the addition of 3 to the front of the list it used to represent.

The abstract data type List can be represented by a linked list data structure, and the abstract data type Tree can be represented by a linked tree data structure. So the classes for List and Tree have a nested class inside them giving the class for the cells of the structure, a single private field holding the structure, and a private constructor which takes a linked structure as argument and constructs a new object to hold it. We saw, however, that as an abstract data type can be represented in any way so long as it gives the methods required with their correct behaviour, we could use other representations than linked structures. We saw an implementation of List where the data structure used was an array and count rather than a linked list. It turned out to be easier to program if the data in the array was held "backwards", that is with the last item in the list in the first cell of the array, the second to last item in the lsit in the second cell in the array, and so on.

We also saw how objects of the abstract data type List and Tree could themselves be used as the data structure to implement the abstract data type Set. What was needed was operations on List and Tree objects which implemented the set operations add, delete and member.

Operations for manipulating List and Tree values are very similar to constructive operations on linked lists and linked trees. The main difference is that there is no destructive alternative - we can only build new structures representing any desired change. Code for the operations is often best written recursively. To construct a new tree representing a change to an old tree, for example, we get the new left branch representing the change to the old left branch, the new right branch representing the change to the old right branch and make a new tree with the new root item representing the change to the old root item, and the new left and right branches. If the left branch or right branch is unchanged in our operations, we can use that branch directly in constructing our new tree. This results in some cells being shared between the structures representing the new and old tree. This is not a problem, since there are no destructive operations, so no chance that a destructive change to one structure will have the unexpected possibility of changing another which shares its cells.

With objects of type List, operations to build a new list can be done iteratively, moving down the original list and building up a new list using cons. However, the items in the new list will be in the reverse order to the old list, so the same technique would have to be used again to reverse them and put them in the correct order. We saw this done with the quicksort algorithm applied to lists, with the append and filter operations it uses implemented both recursively and iteratively.

The code covered in the lectures this week is in the classes List, ArrayList, Tree, IntSet19, IntSet20, UseLists2 and UseLists2a.

Notes covering the material of this week are given in Lists, Quick Sort with Lists and Sets Implemented Using List and Tree ADT.

Week 10: 15/16 March

We started off by considering what would happen if abstract data type List were destructive rather than constructive. If it were, if list referred to an object of type List then list.tail() would change that object so that the first element of the list was removed, while list.cons(n) would change the object so that the content of variable n is added to the front of the list. In fact a destructive list is identical to a concept you may have seen before (for example in the Computer Architecture course), the stack. By convention stacks are thought of as being laid out vertically with an operation to add a new element at the top, or to take the top element off, but obviously that has no real bearing to how they are represented in a computer.

With stacks, the operation to change the stack by taking off the first element (equivalent to a destructive tail) is called pop, while the operation to add a new first element (equivalent to a destructive cons) is called push. The equivalent to list operation head is called top - calling this on a stack returns the first element without changing the stack, so it is actually no different than head. In some implementations of stack, the pop operation both changes the stack by removing its first element and returns that first element, in other words combining it with top. However, we shall keep a clear distinction between operations which return a value and operations which are purely destructive, so we implement pop with a method that has void as its return type.

An implementation of stacks using linked lists is similar to an implementation of the abstract data type List using linked lists. A stack object has a single field referring to a linked list. However, the linked list this field refers to is itself changed in the pop and push methods, whereas with List it was unchanged and a new object needed to be created with the new linked list representing the change in its linked list field.

We noted that whereas up to now we have been considering data structures which hold data of type int, in reality we would want data structures which could hold data of any type. We could build a data structure which holds data of some particular type we are interested in. However, Java being object oriented with its notion of types and subtypes has the built-in type Object which is the most general type. We noted if we used Object rather than int as the data in stacks, and in our other structures, we would have general data structures which could be used to store data of any type. An Object variable or field can refer to an object of any type. Although it can't store primitive data (that is, the numerical and character types) Java has the concept of wrapper classes which are provided in its library and can be used to "wrap up" primitive data into objects. For example, the type Integer is used to "wrap up" data of type int.

Actually, the latest version of Java (1.5) has a more sophisticated way of dealing with generalising data structures to hold data of a variety of types called "generic types". However, that would reqire a lot more work to go into, so we will stick with the simple way that has featured in versions of Java up till now, which is to build structures containing fields of type Object.

A stack is sometimes referred to as a LIFO data type, standing for "last in, first out" meaning that when you take items out of it, the first item you take out will be the last one that was put in (FILO can also be used, it means the same thing since when taking items from a stack, the first item that was added to the stack is the last item that can be taken from it). Taking things the other way round, we could consider a FIFO data type, meaning "first in, first out". Another name for this is queue, called this because it works exactly like a queue in real life, a queue of cars waiting at a traffic light (assuming only one lane and no overtaking), a queue of people waiting to buy a ticket and so on. The first person entitled to leave a queue is always the person who was the first to join it out of all those currently in it. As with stacks, in our version we distinguish between the operation which returns the first item in the queue but does not change the queue, and the operation which takes off the first item but does return anything, calling these first and leave respectively. The operation for an item to join the queue is called join.

A queue could be implemented by a linked list, in which items are taken from the front as with stacks, but when a new item is added, it is added to the back of the linked list. We might consider running a pointer down the linked list to reach the end so we can add a new cell there every time we add a new item, but this is inefficient. A better way to implement queues is as a linked list, but with a separate pointer to the last cell directly accessible from the queue object. So a queue object has two fields of type Cell, where this type is the type used for building linked lists, one of which must always point to the back of the linked list while the other points to the front.

A queue data structure could be used in any program where we want a queue of things working as a real life queue works. Another use of queues is for breadth-first traversal of trees. This means looking at the item at depth 0 in the tree (i.e. its root), then all the items at depth 1, then all the items at depth 2, and so on. This can't be done using simple recursion since it means going to and fro between the subtrees. But it can be done using the following algorithm: construct a new empty queue to store trees, then add the tree we want to traverse breadth first to the queue, then repeatedly take the first tree off the queue, process its root and put its branches back on the queue, finishing when the queue is empty.

We also saw that we can use a stack in a similar way to traverse a binary tree in-order without using recursion. In this case we construct a stack which contains trees and data items. Repeatedly we take the first item off the stack, if it is a data item we process it, if it is a binary tree we put its right branch, then its root, then its left branch on the stack until it is empty.

We noted that when we remove items from an object of an abstract data type storing data items of type Object, we must use type casting to be able to refer to the data items as being of the type they originally were. For example, if q refers to a queue of trees, and variable t is of type Tree, to take the first tree from the queue and set t to refer to it, we must use t=(Tree)q.first(). The reason for this is that the first operation is defined as returning an object of type Object, and so even if we know it must really be of type Tree, we have to put the (Tree) in front of it to allow a variable of type Tree to refer to it.

When we used a stack to traverse a tree, we had a stack containing two different types of data - trees and the data items in the tree. Therefore when we took an item off the stack we had to test what its real type was. This involved using Java's instanceof keyword. If T is a type in Java (including any class name we have written) and v is a value of some supertype of T, then v instanceof T will evaluate to true if v refers to something which is of type T, and to false otherwise.

The code covered in the lectures this week is in the classes Stack, Queue and IntSet21.

Notes covering the material of this week are given in Set Maintenance with a Multiple Undo and Stacks, Queues and Recursion Elimination.

Week 11: 22/23 March

We looked briefly at doubly linked lists. This is a list structure in which each cell has two recursive fields. However, these recursive fields are restricted to be set so that one forms a line of links going one way along a list of cells, the other forms a line of links going in the reverse direction. If the two recursive fields are called prev and next, then if there is a reference to any of the cells in the list in ptr, then either ptr.next is null indicating ptr refers to the first cell in the list, or ptr.next.prev is equal to ptr. Similarly, either ptr.prev is null, indicating ptr refers to the last cell in the list, or ptr.prev.next is equal to ptr.

One possible use of doubly-linked lists is to implement a list with an insertion point, which is similar to the "sequence" we saw earlier. In such a list, the only item that may be deleted at any time is the one currently at the insertion point, and when a new item is added it is always at the insertion point. There are also operations to move the insertion point up and down the list. The operations to add and delete data items have to set the links so the doubly-linked list property is maintained.

Another way of implementing lists with an insertion point is using two stacks. One stack represents all the items before the current insertion point, the other stack represents all the items after it. When an item is added it is added at the top of the before stack, when an item is delted the top of the before stack is removed. To move the insertion point forward, the top item of the after stack is removed and put on the before stack, and to move the insertion point backwards the top item of the before stack is removed and put on the after stack.

We next considered the idea of the abstract data type Table. Another name which is often used for this abstract data type is Map. The idea is that this stores a collection of data indexed by a key, where every item that may be stored in the table has a unique key. The operations on a table are to add a new item (generally done destructively), and two operations which take a key - one to take a key and retrieve the item in the table with that key but without changing the table, the other to delete (generaly destructively) the item in the table that has the that key.

Our implementation of the Java type Table was through a Java interface. This gives a Java type defined purely in terms of the methods that may be called on it, since it contains just the method signatures. In this way it fits in well with the idea of abstract data types, enabling a very clear break to be made between the use of an abstract data type as defined by a Java interface, and the implementation as defined by a separate class which implements the interface. This is the same as inheritance, except that where with standard inheritance in Java a class may only extend one other class, a class may implement more than one interface (known as multiple inheritance). A class which implements a Java interface gives code for the methods which have only their signatures in the interface.

Implementation of a table was very similar to implementation of a set. The same sort of data structures could be used - array and count, linked list, ordered tree and so on - as we used with sets, with the same algorithms used to insert and delete items. However, when we looked at sets we concentrated on sets of integers, where we could test whether two integers were equal using the == symbol or whether one integer was less than another using the < symbol. We introduced a general type we called KeyObject which contained just methods to test whether two objects of this type were equal, or whether one was less than another. We used these in the place of == and < as used in sets of integers. The class KeyObject also had an abstract method (that is, only its signature given) for returning the key of an object of that type. So KeyObject was an abstract type, giving just those operations needed for use when it is used to build up tables. When we want to use tables in practice we would define further types which extend the abstract type KeyObject to store whatever further information we require in practice. This means the code for tables is generalised and can be used to store a variety of different types of objects.

We saw one example of a class that extends KeyObject, enabling us to use it to build a database of student records. This class had a constructor which took a BufferedReader as its argument, enabling us to construct new objects directly from readimg from a file.

We noted that one implementation of sets of integers we could not transfer directly to tables was the implementation as arrays of booleans, where the cell a[i] was true if i was in the set, false otherwise. However, a similar technique could be used called a hash table. The idea of a hash table is that we have a method which given the key of an object returns the index of a cell in an array. This is called the hash function. Then if we have a key, we can find the item with that key in the table by looking in the cell given by the hash of the key. This means we do not have to search for it, so the operations to add, delete and retrieve items from a hash table are all O(1), done in a single step.

The big problem with hash tables is that in most cases we cannot have an array where there is a separate cell for every possible key. Therefore there is a possibility that two different keys will hash into the same cell, so two different objects shoud be stored in a single array cell. This is referred to as a collision. Techniques for dealing with collisions will be covered next week.

The collection of Java classes which together implements a student database is given in the directory table1, which includes a readme file describing the database program and the files used to implement it.

The files ArrayStack.java and ArrayQueue.java give array implementations of stacks and queues. The file InsertList1.java gives a list with an insertion point implemented using doubly-linked lists, and the file InsertList2.java gives a list with an insertion point implemented using two stacks. These are used in Editor1.java and Editor2.java to build a simple text editor program.

Notes covering the material of this week are given in The Editor Example, Stacks, Queues and Lists Implemented Using Arrays and Tables.

Week 12: 29/30 March

We looked at two ways of dealing with collisions. One known as linear probing stores a data item in the next free cell if the one it should go into according to the hash function is occupied. Using this technique, retrieving or deleting a data item using a given key involves looking at the array cell given by the hash of that key, but if it is occupied by a data item with a different key, keep on looking at the next cell in the array until either one is found that has the key being looked for, or a cell is found which is unoccupied (meaning no data item in the collection has the given key). However, as a complication, consider the case where a data item was displaced due to its cell being occupied by another one, but that other one was later deleted. If we were searching for the displaced data item we could look at the cell where it should be, find it empty and conclude it was not in the table. To avoid this, when an item is deleted it is replaced by a special marker. When searching for an item, if the cell looked at contains this special "deleted" marker, search carries on to the next cell because the item being searched for may have been displaced by the item that was deleted and replaced by the deleted marker.

The other way we considered for dealing with collisions is called separate chaining. In this case, each cell in the array contains a linked list of data items rather than a single data item. Collisions are resolved by extending the linked list.

Good hash functions are designed so that data is spread evenly across the array and collisions are rare. This means that the linked list in separate chaining should rarely be long, and the search of extra cells in linear probing should rarely involve many cells. However, it is essential when programming these structures to make sure the code deals with all possibilities.

The next topic we looked at was enumerations. An enumeration is a way of going through all the items in some collection of data. We could be going through them to print them on some file, or to find items with a specific property, or for other reasons. The important thing is that enumerations provide us with a general way of going through all the items in any collection without reference to the implementation of the collection, or the reason why we are going through it.

The type Enumeration is in fact provided as part of the library that is part of the Java system. It is in the library package java.util, so any class that needs to access it can do so by having import java.util.*; at the top of the file. The type is given by a simple interface:

interface Enumeration
{
 boolean hasMoreElements();
 Object nextElement();
}

So if we have a collection of records, say of type Student, with the collection referred to by variable coll, the following code:

Enumeration enum=coll.getEnumeration();
while(enum.hasMoreElements())
   {
    Student stud = (Student) stud.nextElement();
    ...
   }

The definition of the method getEnumeration inside a class for a table or some other collection showed another example of the use of a nested class. In this case, the nested class, unlike the Cell classes we used for linked structures, was not declared as static. This meant that when an object of that class was created its code could refer to the private fields of the object the call to create it was attached to. Our nested class was called MyEnumeration and implemented the java.util interface Enumeration. This meant even though the class MyEnumeration was private, the method getEnumeration could return objects of that class which other classes could treat as being of type Enumeration. So a MyEnumeration object would have some sort of record to a position within the data structure that implements a table which is updated each time nextElement() is called on it.

This was the last topic covered in the course, and was completed in the first lecture of the week. Although the course notes include two further topics, graphs and heaps, these were not covered in the course this year and will not appear in the final exam. The last lecture was a revision lecture which summarised the course. It went through the topics of the whole course, which ar roughly all those terms given in bold face in these lecture notes.

The code covered in the first lecture can be found in class ETable1 which implements interface ETable and StudentDatabase8 which provides a simple student database program which makes use of enumerations. The class Student gives the type of object to go in this database, and it extends the abstract class KeyObject.

Notes covering the material of this week are given in The Student Database Example Part 1, The Student Database Example Part 2 and The Student Database Example Part 3.