Algorithms and Data Structures 2003: Lecture summary

The recommended text book is Data Structures and Other Objects Using Java by Michael Main. Although we won't be making close use of this book, it covers roughly the same topics as the course will cover, and it is always helpful to have an alternative explanation of topics to the course notes, and further examples. To fit in with the order topics are covered in Programming 1 and Programming 2, we will be taking what Main calls (page ix of the book) the "early recursion / early sorting" ordering. This is to avoid discussion of objects and classes until you have at least covered something about them in Programming 2.

It was noted that one way of covering algorithms would be a theoretical and mathematical one, in which the emphasis is on proving that algorithms are correct, and showing the expected time and memory requirements an algorithm may require, along with best and worst cases. We will cover this only to the extent of giving you some feel for this sort of analysis, but this approach to algorithms is covered in more detail in the third year course unit Algorithms and Complexity. The main emphasis in the Algorithms and Data Structures course will be on programming, taking the concepts that were introduced in Programming 1 and Programming 2 and making use of them. It may be considered, then, as a third programming course.

We considered just one problem in Week 1, the Powers example. If we have two numbers, n and m, how can we evaluate n to the power of m (defined as "n multiplied by n multiplied by ..." m times, that is m number of ns multiplied together)?

We first looked at an iterative solution, that is, one using loops. This is probably the first way you would think of solving it. You start off with a variable set to 1, then repeatedly multiply it by n until you have done so m times. We looked at the concept of a loop invariant which can be used to prove iterative algorithms correct, and saw a suitable loop invariant in this case. A loop invariant is a relationship between the values in the variables which is true before execution enters the loop, and can be shown to remain true after each time the body of the loop is executed. When execution of the loop ends, the loop invariant is still true but we know the condition given for the loop to continue must be false. From the combination of the loop condition being false and the loop invariant being true, we can prove we have the solution to the problem.

Next we looked at a recursive solution to the problem. Recursion involves solving a problem by solving a smaller version of the same problem, and using that solution to give a solution to the whole problem. For example, we know that n to the power of m is equal to n to the power of m-1 multiplied by n. The advantage of doing this is that we can us the same code that was used to solve the original problem to solve the smaller version - we can write a method that "calls itself". Since we solve a problem in terms of a smaller version of the same problem, we will eventually reach the smallest version of the problem which can be solved simply without any further consideration, this is known as the base case. In the powers example, the base case is when we want to find n to the power of 1, which is just n.

We can use the concept of induction to prove that recursive algorithms are correct. Using induction informally, that is assuming the recursive call works and seeing that on this basis the full code works, is the way to get to grips with recursion. Many people seem not to find this an easy step to take, hence recursion's reputatation as a "difficult" topic. However, once you have got used to "thinking recursively", it is often an easy way to develop new algorithms, and it is something that any good computer scientist should find natural to use when appropriate.

Using this idea of thinking recursively, we noted that an alternative way of thinking about calculating n to the power of m was to consider that it is the square of the number obtained by raising n to the power of half of m (to take into account odd numbers, if m is odd, round its half down, get the square of raising n to that power, then multiply by another n). The point here is that the recursive call is with m half of the previous value, rather than one less as in our first recursive algorithm. So the number of calls we make until we get to the base case is the number of times we can divide m by two rather than the number of times we can reduce it by one. We noted that if m was large (consider a million) this could make a dramatic difference. We noted that the number of times a number can be divided by two is its logarithm to the base two, which is proportional to its logarithm to any base.

As a final point, we noted the new code we introduced was more efficient because it made one method call to calculate n to the power of half of m, and stored the result in a variable to be used twice in calculating its square. The efficiency gain would be lost if we calculated n to the power of half of m and then calculated it again to multiply and get the square. The Java execution algorithm does not "remember" the result from a method call itself, so if asked to make a call to a particular method with the same arguments as used before, it will go ahead and repeat the calculations it made before. In general, if you find you are making a method call with the same arguments more than once in some code, you should make it just once and store the result in a local variable for re-use. Sometimes this will result in a trivial increase in efficiency, but here where it means a recursive call is made once rather than twice it stops an "explosion" of recursive calls.

Week 2: 20/21 January

We looked at two representative search algorithms, selection sort and merge sort. There are many other sorting algorithms, but these two are enough to illustrate the points that need to be covered.

Selection sort is developed by thinking iteratively about the problem. If we find the smallest item in the array and swap it with the first item, the second smallest and swap it with the second item, and so on, we will end up with a sorted array. Conventionally, we discuss sorting in terms of arrays of integers, though in reality we could use the same algorithm to sort collections of any data type providing we have an ordering on objects of that data type. So by "smallest" we actually mean "the item that is less than all the others in the ordering used for sorting".

Merge sort is developed by thinking recursively about the problem. If we divide the array into two parts, simply by "cutting it in half", and sort each of these parts, we can then merge the two parts together to get a sorted array. Merging means going through two sorted arrays, taking whichever is the smallest of the next item to be considered from both arrays and putting it into the final array. This algorithm is recursive because it involves solving a smaller version of the same problem (sorting the smaller arrays obtained by cutting the original array in half), its base case comes when we consider an array of length just 1, which needs nothing doing to it to sort it.

We noted that a feature of Java is that if an array is passed as an argument to a method, and the contents of that array changed in the method, those changes remain once the method has finished. The same cannot be said for primitive variables like integers passed as arguments. We will discuss why this is in more detail later, but this week it was noted this means there are two varieties of methods which manipulate arrays. A destructive method has its effect by changing the contents of the array passed to it as a parameter, it doesn't return anything, so its return type is given as void in Java, and a call to it is a separate Java statement on it own. A constructive method works by constructing a new array with the desired changes while leaving the array passed as a parameter unchanged. The return type of a constructive method will be the type of the array, and a call to the method only makes sense if it is part of a statement where the array returned is passed on to be used elsewhere, either assigned to a variable or used as an argument to another method call.

We looked at linear search and binary search for an item in an array. Linear search involves going through the items in the array one at a time until the desired item is found, or the end of the array is reached. Binary search only works with arrays that are ordered. It involves looking at the middle item. If the middle item is the one we are searching for, we have found it. If the middle item is greater than the one we are looking for, we can concentrate search on the items before it in the array. If the middle item is less than the one we are searching for, we can concentrate search on the items beyond it in the array.

Binary search can be expressed as recursive code since it makes sense to think of this algorithm recursively. A direct recursive call would take as its arguments a new array representing the half of the array being searched in the recursive call, and the item being searched for. However, this involves unnecessary copying of data into the new array. A better approach is to pass the bounds of the portion of the array being searched as arguments to the recursive call along with the original array. In order that the initial call to the search method does not have to have arguments for the bounds, a technique was used which you will find quite common: there is a public method, and a private method of the same name. The body of the public method contains just a call to the private method which contains the additional arguments (in this case the bounds) which the private method uses in its recursive calls.

A couple of minor Java programming points were covered when considering search: short-circuit operators and bodyless for-loops. The operator written with a double ampersand, && means logical 'and', just like the single ampersand operator & does. The difference is, for any A and B, the expression A&B always evaluates both A and B, whereas A&&B evaluates B only if A evaluates to true. This is useful in an expression like i<a.length&&a[i]!=n, since it means there is a check on whether i is less than the length of array a before an attempt is made to look at a[i]. If there were no such check, the attempt to access a[i] would cause execution of the code to be halted and an exception thrown. The double-bar operator || similarly means logical 'or' like the single-bar operator |, but A||B evaluates A first, and only evaluates B if the evaluation of A comes to false.

A for-loop has the form for(initialisation;test;update) body . If the body consists of several statements, that is indicated by enclosing them with "curly brackets", { and }. But a for-loop may have no statements in the body, this can be shown by the body consisting of just the opening and closing curly brackets with nothing in between, {}. Another way of showing the same thing, is to make the body just a single semi-colon, ;, although it's easy for the human reader to miss this, so {} is preferable from the point of view of making your code easy to understand at a glance. Execution of a body-less for-loop means executing the initialisation then the test, then (unless the test fails first time), repeatedly the update and the test until the test fails.

We finally took a quick look at how we can rank the efficiency of algorithms. Linear search for an item in an array of N items could look through all N items, and if the item occurs in the array but is distributed randomly will involve looking at on average N/2 items in the array. We therefore describe linear search as of "order N", abbreviated to O(N). Compare this to binary search, where the maximum number of items we have to look at in an array of length N is the number of times we can divide N by two, which is the logarithm of N to the base 2, so we describe binary search as of the order log N, abbreviated to O(log N).

In selection sort, we make N(N-1)/2 comparisons of items, or (N²-N)/2. For large values of N this approximates to N²/2. From this, we say that selection sort is O(N²).

With merge sort, the array of length N is divided into two parts, each of which is sorted, then it requires about N comparisons to merge the two parts back into one array. But the two parts are divided into a total of four parts, and in all it requires about N comparisons to merge the sorted four parts back into two. This process of dividing and merging continues for the number of times N can be divided by two, which is the logarithm of N to the base 2. So there are log₂ N lots of N comparisons in total. From this, we say that merge sort is O(N log N). It can be seen that for large values of N, the value of N log N is much smaller than the value of N². This means that merge sort is much more efficient than selection sort.

The important thing here is that for large amounts of data, the efficiency of a program that manipulates that data is dependent on the algorithm used for that manipulation, and not on minor coding details. So if we want to write efficient code, we have to concentrate on getting the algorithms right.

Week 3: 27/28 January

Next we moved on to discussion of environments. When a method is executed, it is executed in its own environment. This means it has access to its own variables, which will be those which are its parameters and variables declared locally within the method. We ignored at this point variables declared in a class rather than a method (either as static i.e. "class variables", or not static i.e. "instance variables"). When execution of a method is finished, the code after the method call is executed, returning to the original environment before the method was called. The effect can be considered as creating a stack of environments, calling a method adds an environment to the top of the stack, finishing a method removes the top environment and execution continues in the one below that which becomes the new top.

The same applies to recursive calls. When a method makes a recursive call, a new environment is created, it will have the same variable names as the old environment but they are separate variables. Whatever they are set to does not change what the variables in the old environment are set to, and the old environment is returned to when the recursive call finishes.

It was noted that in Java passing a variable as the argument to a method can be considered as assigning the value of that variable to a new variable which is a parameter of the method. In Java, assignment of a primitive value, such as an integer means it is copied to the variable being assigned to. But assignment of any other value means the variable being assigned to is set to refer to the same value as the variable being assigned refers to. This is referred to as aliasing, since you can think of it as two names being given to one object, or the object acquiring an "alias". Aliasing applies to arrays. This is why when an array is passed as an argument, even though the method has a separate variable to refer to it, the variable refers to the same array as the argument variable. The result is that changes which take place to the array as the method is executed are permanent, remaining in existence after the method has finished.

We introduced the term tail recursion, which is used to describe cases of recursion where the result of the recursive call is passed on directly with no further computation as the result of the method that made the recursive call. In this case, the stack of environment created by using recursion is not needed as the old environment is not returned to for further computation. A tail recursive method can be converted into an equivalent iterative one. In the iterative version, the equivalent of the new environment is obtained by changing the values in the variables of the existing environment and looping rather than making a recursive call. We developed binary search by thinking recursively, but using this technique of converting tail recursion to iteration, we end up with the version of binary search you saw in Programming 1.

We moved on to a new topic, how we might represent collections of data which may be updated by adding or deleting elements. The only structure for collections of data which you have seen so far is the array. But arrays are of fixed size once created. If you wanted to add or delete an element from a collection of data stored in an array, you would have to create a whole new array one cell bigger or smaller than the previous array and copy the data (plus the added element, or minus the deleted one) into it, which is clearly inefficient. One way of overcoming this is to use an array and count pair to represent the collection. The array is created of the maximum size we would ever want the collection to be. The count states the portion of the array currently used to store data that is considered part of the collection, if it holds the integer n then the first n cells of the array are considered to form the current state of the collection. We can put a new item at the cell indexed by the count and increase the count by one to represent adding a new item to the collection. To represent deleting an item from the collection, we copy the last item in the collection into the cell where the item to be deleted was stored and decrease the count by one.

The problem with this was coordinating the variables representing the count and the array as a pair. It would be a mistake to change one without making the appropriate change to the other. We showed that a much clearer program could be obtained by making them the fields of an object. Then it is clear they are a pair. Also, as private fields, they cannot be manipulated except through the methods of the object. So the object has methods which manipulate the array and count to represent adding and deleting elements to the collection.

In fact, the part of the program that uses the collection object need not be aware of what is inside that object. This is the principle of information hiding. Restricting the ability of one part of a program to manipulate data means the program is easier to understand, and less likely to contain mistakes caused by unexpected interactions. We can mentally break the program into separate parts rather than be forced to view it as one big lump of code. We can work on one part without having to know what happens in another part. So in this case, we have one part of the program which uses sets, and another part of the program in a separate class which provides an implementation of sets.

We showed another advantage of breaking programs into separate classes is that it means the representation in one class can be changed without having to make any changes in the class which uses it. A completely different representation of sets of integers is as an array of booleans, where the cell indexed by n is true if n is in the set, and false otherwise. Obviously, this representation requires a guarantee that integers in our set will only come from a certain range. If we have this requirement, it is a very efficient representation. We could change our set manipulation program to use this representation simply by changing the name of the class it uses to construct its set objects. The reason for this is that the only interaction it has with the sets is the methods it calls, and so long as the method names and argument types remain the same, changing what happens inside the object when the methods are called does not have any effect on how the object can be used.

Week 4: 3/4 February

We considered another possible representation of sets, using an array of the same length as the set. In that case, adding or deleting a number from the set involved constructing a complete new array with the required addition or deletion, and replacing the array in the set object with the new one.

We noted that as assignment of one object to another causes aliasing, we might want an additional method in our set class which returns a copy of a set object. So, for example if s and t are variables of some set type, t=s.copy() would set t to an object which represents the same set as s, but is not the same object. This means if s is changed t stays the same, and vice versa. We demonstrated the use of inheritance to create a class which added a copy method to an existing set class. Also required was a private constructor, one which took as its argument the data structure internal to an object and created a new object with that data structure in it. Such a constructor could only ever be used by methods within the class of the object.

The next example we saw gave a constructive implementation of sets. Up till now, our sets have been destructive, so for example the method call s.delete(7) will change the object referred to by s to represent deleting 7 from the set. A constructive implementation means that calling s.delete(7) makes no change to s but instead returns a reference to a new object which represents the set s represents but with 7 deleted. Since it returns a value but makes no change, s.delete(7) makes no sense as a statement on its own, it only makes sense if the value returned is used, for example assigned to another variable as in t=s.delete(7).

Constructive methods on sets again made use of a private constructor. A new data structure representing the new set was constructed, and this was passed as an argument to the private constructor to create a new object which held the new data structure. In the code for constructive implementation of sets we also saw the use of the keyword this, which can only be used in non-static methods and means "the object this method call was made on". It is used because, for example, s.delete(7) returns a reference to s rather than to a new object, hence this in the method delete, if 7 does not occur in the set represented by s. Although this causes aliasing, it's not a problem because without any method which actually changes an object destructively there can't be any unexpected side-effects caused by aliasing.

Week 5: 10/11 February

The important thing is that so long as the methods that give an abstract data type behave according to the axioms that define it, we have a correct implementation of the abstract data type. The object that the methods work on could use any suitable data structure internally to represent the abstract data type.

We can easily add axioms which define the operations union and intersection on sets, to give us an abstract data type set which is similar to the set concept you will see in a discrete structures course. We looked at writing union and intersection methods which used the add method, but noted that for a constructive implementation of set this was inefficient, because each time the add method was called a whole new set object was constructed. So we gave some code for a union and intersection method working on sets stored as ordered arrays of the size of the set, which went through the arrays representing the two sets being involved. The code was similar to that we saw previously with merge sort.

We noted that if array was the name of the array field in a set object, and IntSet union(IntSet set) the header of the union method, then given the call s1.union(s2) inside the code for this method the array for s1 is called this.array and the array for s2 is called set.array. In general, code in a method in a class can refer to the private fields of the object the method is called on, and also the private fields of any objects of the same type passed to it as arguments.

We looked briefly at an abstract data type called sequence, mainly to illustrate the concept of abstract data types. A sequence is an ordered collection of items which has an "insertion point". When we add an item, the item is added in the insertion point. The delete operation can only delete whatever item is at the insertion point. There are forward and backward operations which move the insertion point one position up or down the collection. The abstract data type is defined by these operations, and not by any particular representation on the computer. You can see code which uses and defines sequences here. It is divided neatly into two files, one (UseIntSequences.java) a "front-end" which uses sequences and provides a simple program a human can use, the other (IntSequence.java) giving an implementation of sequences, in this case using a partly-filled array and two integers.

Next we started on the important topic of linked lists. A linked structure consists of objects of a recursive type. Just as a recursive method is a method that has calls to the same method, so a recursive object has fields of the same type as the object (as with methods, there is also the possibility of indirect recursion). Linked lists are the simplest type of linked structure, an object of a type representing a linked list has a data field, and a single field of the same type. The field of the same type itself refers to an object with a data field and a further field of the same type, and so on. We can think of these fields of the same type as links in a chain, or pointers, and the individual objects as cells, and show the situation diagrammatically as a cells and pointers diagram. Note that where we say "field" here, we mean what is referred to in Java as "instance variable".

Linked lists are not infinite, because the linking recursive field, like any object variable, may be set to null meaning "refers to no object". There is also the possibility that the field is set to refer to a cell already in the list, leading to a circular list.

We did not declare the fields in our cell objects as private, hence they could be changed by code in other classes. Thus a linked list, as we defined it, is a data structure not an abstract data type, since it may be changed by referring to the cells and pointers directly, not through methods provided by the linked list cell class. We saw examples of operations on linked lists. Crucial to understanding these operations was to note how aliasing works: if a and b are variables of an object type, then b=a causes b and a to refer to the same object, so if that object type has a field called next, a.next and b.next are the same piece of store in the computer. So changing b.next automatically changes a.next as they are two names for the same thing. However, assigning a to refer to some other object, as in a=c does not change what b refers to, it still refers to what a used to refer to.

If next is of the same type as a, then we can refer to a.next.next, meaning "the next field of the object referred to by the next field of the object referred to by a". We will often say "a" when we mean "the object referred to by a", so we could shorten that to "the next field of the next field of a". Remembering to say "the object referred to by a" is a way of reminding us that other variable names may refer to the same object, and a may be set to refer to another object during the course of execution of the program.

Week 6: 17/18 February

Operations on linked lists often involve setting a pointer to refer to the first cell in the list, and then moving it down the list until some condition is met. If we use the variable name ptr for the pointer, that is achieved by ptr=list, followed by repeating ptr=ptr.next until the condition is met. If we want to set the pointer to the last cell in the list, the following will achieve that:

for(ptr=list; ptr.next!=null; ptr=ptr.next) {}

The following will cause ptr to refer to the cell before the cell whose data is n:

for(ptr=list; ptr!=null&&ptr.next!=n; ptr=ptr.next) {}

We used the above to give methods which manipulated a linked list to add and delete integers. The methods assumed the existence of a list as a "global variable", they did not take the list as an argument. This made sense when these methods were non-static and part of a class describing an object which had a linked list field. Calling the method on the object manipulated the linked list of that object. This gave us another way of representing sets. So, for example, calling s.add(3) manipulated the list field of the object referred to by s to add a cell storing 3 to it. We made the Cell class a nested class, that is a class declared inside another class. Java allows this, it means the nested class (assuming it is declared as private) can only be used by the code of the class it is declared within. We have split programs into a front-end part which uses an abstract data type, and an implementation part which gives the code that makes the abstract data type work. Making a class like Cell which is only needed for the implementation, a nested class is a good way of keeping that strict division between the different parts of the program.

We also looked at ways of constructing linked lists using recursion. If list is a list as given above, then if it is null, then null is its copy, otherwise new Cell(list.first,copy(list.next)) is its copy. If we wanted to use recursion to manipulate the linked list representing a set in a set object, we needed a public method which calls a private static method with the linked list of the object as its argument, the static method then does all the work by calling itself recursively.

Next we looked at binary trees. Linked lists are made up from cells which has one recursive field, binary trees are made up from cells which have two recursive references. Conventionally, these two references are called the "left" and "right" branches. The first cell in a tree is called its "root", and while the whole structure may look like a tree, it is drawn diagrammatically with its root at the top! Any cell in the tree may have one or two branches set to null.

An ordered binary tree has the property that all the items in its left branch are less than its root item, all the items in its right branch are greater than its root item, and the two branches are similarly ordered. This can be used to represent a set. To determine if an item is a member of the set, check if it is at the root. If it is, it is in the set, otherwise go to check either the left or right branch depending on whether the item being checked for is less than or greater than the root item. It can be seen that each time we go to the left or right branch, we cut out half the items from consideration without looking at them (assuming the branches are equal in size, which may not always be the case). Thus searching for an item is rather like binary search of an array. Compare this to searching for an item in a linked list, where you have to go through the items one at a time, like linear search of an array. Storing a set as an ordered binary tree makes searching for an item in it more efficient.

Adding an item to an ordered binary tree similarly involves moving down its left or right branch depending on whether the item is less than or greater than the root, until a cell is found with an empty branch to its left if the item is less than the value in that cell, or to its right if the item is greater than the value in the cell. The empty branch is then replaced by a cell with the new item as its value and with empty left and right branches.

Week 7: 24/25 February

The really tricky bit comes when we want to delete an item which is in a cell neither of whose branches are the empty tree. We cannot just remove the item and leave a "hole" in the tree. What we can do is replace the item by the rightmost item in the tree's left branch (removing the cell that contains that item from the branch). Since this must be the biggest item in the left branch, making this replacement will keep the ordered property of all items in the left branch being less than the root item, and all items in the right branch being greater than it.

Following this, we considered constructive addition and deletion from binary trees. This means the construction of a new tree which represents the change while leaving the original tree unchanged. We noted that the new tree could share any branch of the old tree when no changes were made to that branch. This sharing will not be a problem so long as we ensure there is no code which performs destructive changes on trees. There won't be if we avoid code which actually assigns values to the fields of cells in a tree. All code in constructive operations on trees will only create new cells. If we want to make a change to the left branch of a tree, we create a new cell whose root item is the same as the root item of the original tree, whose right branch is the same (i.e. shared) as the right branch of the original tree, and whose left branch is the result of the recursive call which creates a new tree representing the change to the left branch. Similarly if we want to change the right branch.

Next, we considered a new abstract date type, the List. Different authors define the ADT "List" in different ways, often more like what we have called a sequence, but our definition is perhaps the simplest one. We define the ADT "List" by just the operations head, tail, cons, empty, and isEmpty. We have a correct implementation of the type List so long as we have methods that perform these operations in accordance with the axioms for lists. The head operation gives the item at the front of the list, the tail operation gives a new list consisting of everything except the first item of the list it is called on. The cons operation gives a new list consisting of all the items in order of the old list it was called on, plus the new item given as the argument to the cons call added to the front of the list. The isEmpty operation tests whether the List object it is called on is empty. The empty operation is implemented by a static method rather than an object method. This is because it is not called on any object. It returns a new object representing an empty list.

Superficially, this looks very like the linked list data structure we considered previously. There, if we had a variable llist referring to a linked list, llist.first gave us the first item of the linked list, while llist.next gave us a linked list consisting of everything except the first item. Now we are saying that if we have a variable list of type List, then list.head() will give its first item, and list.tail() will give the list consisting of everything except the first item.

However, llist.first and llist.next are fields, or instance variables. They can be assigned values as well as used as values. So, for example, llist.first=x changes the first item of the list referred to by llist to x. Whereas list.head() and list.tail() are method calls. You cannot change the first item of the list referred to by list by an assignment, for example, list.head()=x, because that does not make sense in Java. You can only assign things to variables in Java, you can't assign things to method calls. The consequence of this is that our lists using the List type cannot be changed destructively, since the only methods we have available with them are constructive ones.

Having defined the type List in terms of its methods, we need code to give us an internal representation of lists and make those methods work. The natural way of representing a List object is with a linked list. So as we did with sets, we make the Cell class a nested class inside the class for our objects, have a private field of type Cell to store the data structure representing the object, and a private constructor to enable us to create a new object with the linked list we have created in a method inside it.

Just to show that a List object really is a different thing from a linked list, we gave an alternative implementation which used an array and count to represent a list.

Week 8: 3/4 March

We also noted that with the abstract data types Tree and List, an empty tree or an empty list is still represented by an object. This contrasts with the linked structures, where an empty tree or list is represented by null. Since null is not itself an object, you cannot call methods on it, which can complicate programming. In our example code, there is no check that the methods which break up a structure - head and tail for lists, left, right and item for trees, are called on non-empty structures. This was done for simplicity, but it is possible to make these calls since empty structures are represented by objects. We could modify the code to throw our own defined exceptions, but otherwise calling head on an empty list, and so on, will result in a NullPointerException being thrown.

We considered the abstract data type Stack. This is defined by the operation top which gives the first item in the stack, pop which changes a stack to remove its first item, push which adds a new item to the top of a stack, plus the usual operation to test for emptiness and to return a new empty structure. The type Stack can be considered a destructive form of List, with top changing the list to remove its first element rather than returning a new list representing all but the first element, and push changing the list to add a new first element rather than returning a new list representing the addition of a first element.

Stacks are known as LIFO collections of data, an acronym for "Last In, First Out". This means that the only item that can be removed from the collection is the one that was last put in and remains in. A contrasting collection type has the FIFO property, that is "First In, First Out". Here, the only item we can remove from the collection is the one that was added to it first that remains in it. This data type is known as a Queue, as it behaves exactly like the queue we are familiar with in real life when people line up for some service (e.g. a service point in a bank) and they are served in the order in which they arrive.

Both stacks and queues can be represented by linked lists, so the implementations we saw for them had a linked list structure referred to by private fields of the object. However, an efficient way of representing queues has a pointer to the back of the linked list as well as the front. This enables new items to be added to the back of the queue easily, without having to run a pointer all the way down the list which would be required with a standard linked list structure.

We noted that so far, for simplicity, we have mainly considered data structures which are made up of integers. However, data structures may contain objects of any type, we have used integers only because it enabled us to give simple examples. We noted that Java has the type Object, which is the most general type - a variable of field of type Object can be set to refer to an object of any type. Therefore, if we build data structures out of type Object, we can use then to store anything. If we take an object out of such a generalised data structure, however, we have to use typecasting to be able to refer to it by its actual type.

We saw how we could use a queue to traverse a tree breadth first, that is layer by layer. Simple recursion can't do this, because it involves considering part of the left branch, then part of the right branch, then back again and so on. The breadth-first traversal algorithm involves starting with an empty queue and then adding the tree to the queue. Then repeatedly, take the first tree from the queue, perform the desired operation on its root item (e.g. print it), and put its left and right branches on the back of the queue (unless they are empty). Continue until the queue is empty.

If a stack is used in this way rather than a queue, the result is standard tree traversal. However, using an explicit stack means we can do tree traversal without involving recursion, whereas previously we tree traversal involved recursive calls taking the tree's branches as the arguments.

Week 9: 10/11 March

Next we looked at how array implementations of stacks and queues. A stack uses an array and counter, the counter being increased by one and the new object added in the cell it indexes to represent the push operation, and decreased by one to represent the pop operation. Queues may be represented by an array and two indexes, one giving the position of the first element on the queue, the other the position of the next free cell after the last element. When an item leaves a queue, the first index is increased by one, when an item joins the queue, the second index is increased by one. Since with queues, unlike stacks, the indexes are never reduced, they will after a few operations reach the end of the array. A wraparound technique is then used with the indexes set to 0 if they are increased after reaching the end of the array. If the front index is higher than the back, then the portion of the array that makes up the current queue is taken to be starting from the front index to the end, and then continuing from the start

The remainder of this week was concerned with the abstract data type Table. A table is a collection of data items which can be accessed by means of a key. Typically, a key will be a string which is known to be unique for each data item, for example a car registration number if the items are records concerning cars, or a national insurance number if the items are records concerning employees. The operations on a table are to take a key and find the item in the table with that key, to take a key and delete the item with that key from the table, and to add a new item to the table. A table would almost always be destructive (that is the operations change the data structure rather than returning a new table).

In fact a table is very much like the sets we considered previously. The data structures we used to represent sets of integers could more generally be used to represent tables of data. Some of those data structures relied on the fact that integers can be ordered so that we can quickly locate the integer we are looking for. Although the most general type in Java is Object, there is no ordering associated with objects of this type, so we developed a general abstract type which had just the methods in required to order objects by a key associated with them. Being able to generalise like this in an important aspect of programming, particularly in object-oriented languages like Java. We write code using general types, and then we can re-use it many times by applying it to more specific types that extend the general types. Abstract data types are best represented by a Java interface which gives just the signatures of the methods that define them, and which may then be implemented by a separate type which gives the details of the data structure used and how it is manipulated by the methods.

In order to demonstrate how this all fits together, we considered a complete student database program, which can be found here. Note it involves five files in total, one to give the front-end which interacts with the use, one the interface which defines tables, one the implementation of tables, one the definition of the general type of objects that go in tables, and one the specific type which extends that general type to provide useful data objects. The directory also includes a short explanation of how to use the system.

This program also gave us an opportunity to look at simple reading from files in Java. We have already seen, but not really discussed,

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

BufferedReader file = new BufferedReader(new FileReader(filename));

We also considered StringTokenizer, another built-in Java type, this time from the java.util package. Java BufferedReader objects have only code to read whole lines or individual characters. String tokenizers enable strings representing whole lines to be broken up into individual words. If line is a String variable holding a line of text, then

StringTokenizer toks = new StringTokenizer(line);

However, in general there are large numbers of keys and we cannot guarantee that for every key there will be a separate array cell. So we have to be able to deal with cases where two data items would be put into the same cell due to the hash function on their keys giving the same value. This situation is known as a collision.

We looked at two ways of dealing with collisions in hash tables. One, known as linear probing, simply stores the data in the next free cell if the one it should be stored in according to the hash function is already occupied. To find a data item given a key, look at the cell indexed by the hash function of the key. If it is occupied, but the data item occupying it has a different key, look at the next cell, and so on until either we find a cell that stores the data item or we find an unused cell and can then conclude the data item is not stored in the table. Note that if a data item is removed, a special marker has to be put in its place to indicate that it is a cell that was formerly occupied. This is because if we are looking for a data item that has been displaced due to a collision it may have been displaced by an item that has been removed, so the special marker tells us to carry on looking further.

The other way of dealing with collisions we considered was separate chaining. This meant that each cell in the array stored a linked list of data items with keys whose hash function gave that cell's index. If we have a good hash function that ensures data is spread evenly across the array, the linked list should not be long, so searching it for the data item with a given string should not take long.

We next considered enumerations. This is a general way of going through the items in a collection of items. The interface Enumeration is built into Java as part of its java.util package. It contains just two methods: nextElement and hasMoreElements. When we have created an enumeration object on the basis of a particular table or other collection object, the first time we call the method nextElement on the enumeration object, we will get returned the first item from the collection. The next time we call nextElement on the enumeration object, we will get the second item, the third time we call it we will get the third item, and so on. A call of hasMoreElements on the enumeration object will return true unless we have already called nextElement as many time as there are data items in the collection, then it will return false.

We saw how we could add a method getEnumeration to a class for tables in order to provide an enumeration for objects of that class. Since the details of the enumeration, that is how the methods nextElement and hasMoreElements operate, will depend on the implementation of the table, we gave the class for the enumeration object as a class declared inside the class for table objects, implementing Java's Enumeration interface. This nested enumeration class is not declared as static, unlike the nested Cell class we used for linked structures. This means an object of that class has direct access to the fields of the table object it is constructed from a call on. A non-static class declared within a class is known as an inner class.

When we considered constructing an enumeration for tables where the data structure used is a tree, we used the technique described previously, to go through all the items in a tree by means of a stack. This meant our enumeration had to have its own stack made up of cells, and a class for cells was declared inside the class for the enumeration. This was an example of a class declared inside a class declared inside a class.

Note that the type Iterator has largely replaced the type Enumeration in recent Java programming. An iterator has an extra method which enables us to remove objects from the collection. We used the type Enumeration for the purposes of illustration because it is simpler to implement.

Week 12: 31 March / 1 April

An obvious data structure to provide the underlying representation for a priority queue would be a linked list of items in order of priority. However, inserting an item in such a linked list is inefficient because you have to go right through the list up to the point where it should be added, so it is O(N). We discussed an alternative way of representing priority queues called a heap.

A heap can be considered a binary tree structure with the following properties: it must be complete, and at any node in the tree all the items in both the left and right branches must be of lower priority than the item at the node. A binary tree is complete if, viewing it breadth first, each layer in the tree apart from the bottom layer has its maximum number of elements, and the bottom layer has all its elements to the left-hand side. Note the property of a binary tree being a heap is a different property from that of a binary tree being ordered that we considered previously.

When a new item is added to a heap, it is initially put in the leftmost empty position on the bottom layer, but then swapped in position with its parent if the item has higher priority, with this swapping continuing and moving the item up the tree until it is either at the top or has a parent with higher priority than itself. The root item at the top of the tree is clearly the highest priority item of the whole collection. To remove this item, it is replaced with the last item added (i.e. the rightmost item of the bottom layer) and this is repeatedly swapped with the higher priority of the two items at the root of its left and right branches until it reaches a position where it is either in the bottom layer or has no descendant with higher priority. It can be seen that if we take a swap as one operation, inserting or deleting an item from a heap is .

The binary tree of a heap is actually stored in an array rather than the linked structure we used for ordered binary trees. The items in the tree are stored in breadth-first order in the array. The property of the tree being complete means that for any node stored in the cell of the array indexed by i, the roots of its two branches are stored in the cells indexed by i*2+1 and i*2+2, while its parent item is stored in the cell indexed by (i-1)/2. This makes the swapping required to add and remove items easy to achieve. The array for the heap will be partly filled with a count variable stating how much of its is currently in use, with the count variable giving the index of the next free space were new items are initially inserted.

In order for items in a priority queue to be able to establish an ordering between themselves, we made them items of the type Comparable. This is defined by an interface which is built into Java. The interface says that items of this type must be of a type which implements it by providing a method called compareTo which takes an object as an argument and returns an integer as a result. Given two objects of type Comparable, referred to by variables c1 and c2, the method call c1.compareTo(c2) returns a negative integer if the object referred to by c1 is less than the object referred to by c2 in their own ordering, it returns 0 if they are equal, and it returns a positive integer otherwise. In fact, we have already seen the use of compareTo when used with strings, since the type String in Java is a sub-type of the type Comparabale, and the ordering which strings have built into them through this is alphabetic ordering.

This was the final piece of new material for this course. The remaining time was given over to going through last year's exam paper.