Introduction to Programming: Lecture summary

This is a summary of the lectures that were given in the course Introduction to Programming by Matthew Huntbach in the academic year 2000-01.

Week 1
Week 2
Week 3
Week 4
Week 5
Week 6
Week 7
Week 8
Week 9
Week 10
Week 11
Week 12

Week 13
Week 14
Week 15
Week 16
Week 17
Week 18
Week 19
Week 20
Week 21
Week 22
Week 23
Week 24

Note: the additional work links for each week often contain further links to relevant material. These links were live at the time of the lectures, but are often to such things as other universities' lecture notes which cannot be expected to remain available permanently. This page is kept available for archive purposes, I am not intending to maintain it by replacing dead links.

Week 1: 26th September 2000

The first lecture was given by Richard Bornat, as Director of Undergraduate Studies, as a general introduction to learning in Computer Science. This theme, with its central message that learning to program is something you have to do by doing it (and by wanting to have fun doing it!), was continued in the second lecture. Also covered was a general explanation of why we, in common with many (by now perhaps most) Computer Science departments, use Java as the main language to teach programming. But also a reminder that this is a course in "Introduction to Programming" and not "Introduction to Java".

Week 2: 2nd October 2000

Started with a quick run through what a computer is: how the programs we write are in high-level languages which need to be translated to actual machine code instructions a computer obeys, and how when you interact with a computer you are interacting with a program that is already running called the "operating system". Then a description of how a Java program is structured: a collection of classes (each usually in its own file), where a class describes an object. An object is a collection of data with references to some methods (pieces of computer code) that manipulate that data. Some methods (termed "static") are not associated with any object but must still be put within classes.

We looked at two simple Java programs HelloWorld and HelloYou. Both of these are programs so simple that they consist just of a single static method in a single class. The HelloWorld example shows the packaging that is needed in Java to go round a single instruction that just prints a message to the console. The HelloYou program, however introduces a number of new concepts:

Additional work

Week 3: 9th October 2000

We noted that when you run a Java program, you start off executing the instructions in the main method of some class, but those are likely to include calls to other methods in other classes. As well as classes which form part of Java's library, you may also use classes written by yourself or other people.

If you want to use someone else's class, you need to have the .class file for that class in the directory you run the program from (actually there are other ways of doing it, but this involves additional complexity I don't want to go into). Note, you do not need to have the .java file, or even to know what is in it, although obviously you need to know the names of the methods in it and the arguments they take.

This first came up when we noted that because of the complexity of text input and output in Java, many authors of textbooks have introduced their own text input/output classes to simplify it. Versions of the HelloYou program using the text input classes from the Bishop, Barnes and Horstmann textbooks were looked at.

To consider creating and using objects in more detail, we looked at the examples using the Ship class from Chapter 3 of Barnes's book. We noted that calling a method on an object may have one or more of three different sorts of effects:

Additional work

Week 4: 16th October 2000

Started by noting the distinction between static methods (which you have covered in the lab) and other methods (called "object methods"). A static method is "self-contained" - it works with the data presented to it as arguments. An object method may have data presented to it as arguments, but its call is attached to a reference to an object and it also makes use of the data in that object. If a static method from another class is called, the call is attached to the name of the class.

Next we looked at aliasing. If a and b are variables of primitive types (essentially the various number types, plus single characters and booleans), then a=b copies the value from variable b into variable a. Otherwise a=b sets a to refer to the object that b refers to, so a and b can be thought of as two names for the same object, or a "is an alias for" b. Note, if before a=b was executed, another variable, say c referred to the same object that a referred to, although a=b means a no longer refers to that object, c still refers to it.

We noted that if you pass an object where a String is expected (for example in a call to System.out.println, or attempt to join an object to a string using +), what is actually passed or joined is the result of making a call on the toString() method on the object.

Finally, we started looking at structured statements. Up till now we have only looked at programs (and then only at the main method of the program) whose statements are simply declarations, assignments and method calls. But a more complex form of statement is itself made up of statements. We looked at the while statement which consists of a condition and some substatements. The condition is checked, and if it evaluates to false execution goes on to the statement after the while statement and the substatements are never executed. Otherwise, the substatements are executed in turn, and then the whole process is repeated starting with checking the condition again. This continues until a time when the condition is checked and evaluates to false. We also looked at the do statement, which is similar to the while statement except that the substatements are always executed once before the condition is checked.

Additional work

Week 5: 23rd October 2000

Started off by continuing where we left off in the previous week with structured statements. Noted that the statements inside the { and } of a while-loop can be any statements, including further while loops, or variable declarations. A variable declared within { and } can be considered as disappearing from existence when execution reaches the }, we say that its scope is until then, and a new variable of the same name but not the same value is created if the loop is executed again. The statement break causes immediate exit from the loop.

We looked briefly at if statements which you should be familiar with through doing a lab exercise which introduced them.

We noted that the { and } can be omitted from a while or if statement if they enclose just a single statement. If the Java compiler finds no { after the ) following the condition (or following else) it will take only the following statement as forming the loop or conditional part.

Next we looked at the Java primitive types for storing numbers, and the arithmetic operators. We noted that operator precedence resolves the ambiguity of something like a=b+c*d, and the left-associativity of - resolves the ambiguity of something like a=b-c-d. We can assign an int value to a double variable, for example if x is a doublen is an int, we can do x=n, but the other way round requires type casting, for example n=(int)x. As dividing one integer by another gives an integer (rounding down any fractions) we also use type casting if we want the complete value of dividing one integer by another, for example if m is also an int, we need x=(double)m/n to divide m by n and put the result including the fractional part in x. The operator % gives the remainder on integer division.

We looked at the shorthand asignment operators a+=b as shorthand for a=a+b and so on. Also ++a and a++, as an example of something which has both an effect (so it may be used as a statement on its own) and a value (so it may be used in an expression or passed as an argument). In both cases the effect is to increase the value stored in variable a by 1, but the former has the value of a after the increase, the latter the value of a before it.

We noted briefly that a^b does not have the value "a to the power of b" that it has in some other languages, but is instead one of a family of bitwise operators which you needn't consider any further at this stage. We looked at && and || as the boolean operators meaning "and" and "or" respectively (with ! meaning "not"). We noted that the short-circuit evaluation of && and || could be demonstrated by an expression with a side-effect, such as in if(a>b&&b>c++) but on the whole it is not a good idea to have expressions with side effects as they can make programs hard to understand.

We also looked at the conditional operator, a?b:c where a is a boolean expression and b and c are expressions of any type (but they must be of the same type). If a evaluates to true, the whole expression has the value of b, otherwise it has the value of c.

Additional work

Week 6: 30th October 2000

Lectures cancelled due to bad weather making transport from many parts of London and further out difficult or impossible. Please use the opportunity of no new material to catch up on what we have done so far and make sure you thoroughly understand it. Some exercises that will help test your understanding are available from the link below.

Exercises
Answers to exercises

Week 7: 6th November 2000

Mentioned mathematical functions can be found as static methods in the Math class, which is part of the java.lang package that is always available in Java compilation so does not need to be imported. For example, Math.cos(x) represents the cosine of the value stored in variable x (treating it as in radians).

Next came coverage of the char primitive type. Java represents characters using 16 bits rather than the 8 bits used in other languages, so it can represent any of the characters in the "universal character set" called Unicode (a couple of links to pages on this are in the course web page here). In practice, your display is unlikely to be able to cope with more than the first 256 of these, which are equivalent to the ASCII standard. That characters are represented internally by their ASCII code can be shown by assigning a character to an int variable, or assigning the other way (which needs typecasting to convert 32-bit ints to 16-bit chars).

Next we discussed Strings. Note the difference between a String literal (enclodes by double quotes) and a char literal (enclosed by single quotes) e.g. "x" and 'x'. String are objects, with a number of methods provided in the String class which like Math is in java.lang. None of these methods change the state of a String, hence once a String object is created it can never be changed, a property known as being immutable. You need to be familiar with a number of common String methods: length, charAt, subString, equals and compareTo, although there are quite a few more built into Java besides this.

We saw some examples of loops going through the characters in a string using charAt, and these were used to introduce for statements, which are like while statements but with a separate initialising and update section.

We showed how sections of code could be named with values used by them passed in as arguments to static methods. This means the code can be reused with the code specialised for its context by passing in values as arguments.

We looked at string tokenizers which enable whole lines of text to be broken into several words. These are needed in Java because the BufferedReader method readLine reads a whole line of text in one go. To use a string tokenizer you need to import the java.util class. A local copy of the official Java documentation for the class StringTokenizer can be found here.

Additional work

Week 8: 13th November 2000

The first lecture covered exceptions. An exception occurs when during the course of running a program an attempt is made to execute something in a way that can't be done normally. In some languages this would cause the program to halt. In Java it causes the program to throw an exception, and Java uses try-catch to recover from exceptions rather than halt. There are many different types of exceptions. For example, Integer.parseInt(str) is an int value created by considering the characters in the string str to be digits in the decimal representation of an integer. If str does not contain just decimal digit characters, the call will throw an exception of type NumberFormatException

A try-catch statement takes the form

try { code1 } catch(SomeException e) { code2}
If at any time during the execution of code1 an exception of the type SomeException occurs, execution of code1 immediately stops and execution of code2 starts. Note the exception must be named as well as given a type (though by convention it is always named e as above), and the curly brackets are compulsory (unlike with loops and if statements). It is possible to have more than one catch part to a try part to enable several different types of exceptions to be caught and handled differently.

In the above case, once code2 is executed, code1 is not resumed, execution then goes on to the code following the try-catch statement. However, try-catch are often combined with infinite loops, so

while(true)
   try { code; break; } catch(SomeException e) { }
represents repeatedly executing code until it does so without a SomeException ocurring, while
while(true)
   try { code } catch(SomeException e) { break; }
represents repeatedly executing code until doing it causes SomeException to occurs.

In the second part of the first lecture, and in the second lecture we saw for the first time examples of Java classes that define objects. The code for the examples used in the second lecture can be found in the directory /import/teaching/BSc/1st/ItP/accounts.

An object definition consists of some variables, generally declared as private so no code outside the class can refer to them, and some methods declared as public which define how an object of the type defined by the class interacts with Java methods in other classes. The variables are declared outside any method, and are more correctly referred to as fields. Each object of the class contains its own fields. An object does have access to the private fields of another object of the same type if that object is passed as an argument to its methods, in that case, if val is a field and p the parameter to a method, val on its own refers to the object's own val field, while p.val refes to p's val field.

A class may have one of more methods of the same name as the class and with no return type, which are referred to as constructors. A constructor is called to create a new object with the word new. The particular constructor used depends on the number and types of arguments to the call following new. There may also be more than one of other methods of the same name providing the signatures differ in the types and/or numbers of arguments. The ability to have several methods of the same name is referred to as overloading.

Additional work

Week 9: 20th November 2000

The first lecture was used for the first test of the course. The second lecture was left free. A copy of the test paper (in postscript format) can be found here. A copy with the answers filled in can be found here.

Note there was one error on the test sheet: question 3 a) should have started "Write a fragment of code that will print Yes if b has a value that is in between a and c" (i.e. the second b should have been c). There was one error in the hard copy answer sheet that was distributed: in question 4 c) following { there should have been an extra line count++;. These errors have been corrected in the postscript versions available here.

I have also made available some comments on the test results.

Week 10: 27th November 2000

The major thing covered was the idea of inheritance. If we declare one class as extending another, for example:
class BObj extends AObj
{
declaration of fields and methods
}
then the class has all the methods and fields of the class it extends. So here, a BObj object has all the methods of an AObj object without them having to be declared, plus the additional methods declared of its own. Here we say that "AObj is the superclass of BObj" or, alternatively and meaning the same, "BObj is a subclass of AObj".

If a subclass has a method with the same signature as a method in its superclass, the code for that method will replace the code from the superclass; this is known as overriding. The overridden method may be accessed from the subclass by prefixing the call to super followed by the normal . for a method call. The word super is also used (but followed directly with a (, some arguments and a )) to access the code of the matching constructor of the superclass, it can only be used in this way as the first line of a constructor.

Note the code for methods of a subclass cannot refer to the private fields of its superclass, but if fields are declared as protected they can be referred to in subclasses either to get their value or change their value.

Inheritance was illustrated by the Account and DepositAccount classes which can be found in the directory /import/teaching/BSc/1st/ItP/accounts along with some front-end classes (i.e. classes that provide a main method) which use them.

We also looked at switch statements. A switch statement takes the form

switch(exp)
   {
    ... code
    case lit:
    ... code
   }
where exp is an expression which evaluates to either an integer or character, and lit is an integer or character literal, that is either an actual number or an actual character, not a variable. There can be any number of case lit: case labels. Execution of a switch statement first evaluates exp and then goes to the code following the case label whose lit parts matches the result. It executes all the code following it, ignoring any further case labels, until it either executes a break which causes it to exit the switch statement and proceed with the code following it, or it reaches the closing }. In practice, it's usual for a case label to have its own code followed by a break, with the alternative of execution following through to the code for the next case label so unusual that it should be commented if done deliberately.

The case label default: covers all cases not covered by other case labels.

Finally we looked at labeled breaks. A break on its own exits only the innermost loop or switch statement. In some cases a statement which exits out of several loops and/or switch statements which are inside each other is useful, this is what labeled breaks are for. Any loop or switch statement may be given a name by putting before it in the code name: where name is any Java name except a reserved word. Then the statement break name will exit out of all the loops and switch statements it is in, up to and including the one labeled name.

Additional work

Week 11: 4th December 2000

In the first lecture we saw how you could create your own exception types by writing a class which extends Java's built-in type Exception. If a method is capable of throwing such an exception you have to indicate that by adding throws plus the exception type to the signature of the method. A throw statement actually throws an exception - it causes execution of the current method to be halted and execution returns to the point where that method was called. If the method was called within a try block which has a catch part which matches the exception type, then execution moves to that catch part, otherwise it moves up to the next level of method calling, and so on (causing the whole program to "crash" if the execption is never caught). User-defined exceptions are handled in just the same way as system-defined exceptions so far as catching them is concerned.

As an exception is an object, you usually have to create a new one when you throw one. You can pass a string argument into the constructor for an exception, then when you catch it (remembering the catch part has to name the exception, by convention to e) you can access that method by calling the getMessage() method on the exception.

We also saw how when code becomes complex, with loops or switches or try blocks within further loops switches and try blocks and so on, it can make sense to move some of the details off to a separate private method. This also means you can reuse code by calling that method more than once. It's a matter of choice when it becomes best to break up a method in this way, although some authors suggest it should be done once the code in a method becomes so long it can't all fit on one screen or sheet of paper.

The second lecture introduced Java's interface concept. An interface is a way of defining an object in terms of the methods that can be called on it. An interface is generally in a separate file with the normal .java ending. It starts with

interface Name
{
where Name is any name you choose for it (so long as it is a valid name for a Java class). Following this is just a list of method signatures (i.e. the first part of a method up to but not including the method's first {). The file ends with a }.

A Java file can extend another class, shown using the key word extend, but it is also possible for a class to the implement an interface, shown using the key word implement. If a class implements an interface it has to have a full method for each of the methods whose names and types are listed in the interface.

The important thing about interfaces is that a parameter to a method can have the interface name as its type. Then an object of any type which implements that interface can be passed as an argument to fill that parameter. This is a useful way of generalising code. It can, for example, be used to give a similar effect as that given in functional programming where functions are passed as arguments. You cannot pass a method as an argument in Java, but you can pass an object which implements an interface which has that method.

Additional work

Week 12: 11th December 2000

The main topic covered was arrays. In Java for any type X the type X[] is available, with the meaning "array of X". An array type is an object type, so declaring a variable of an array type does not mean an object of that type is created. That has to be done separately (although you can combine declaration of an array variable and initialisation of it to an array object in one statement). If a is a variable of type X[] then a = new X[exp1]; is a statement which creates a new array object and makes a refer to it. Here, exp1 is any expression which evaluates to an integer.

The expression exp1 is evaluated when the program is run, and sets the size of the array created. So the size of an array in Java is fixed at run time (and not at compile time, as with some other languages). Once an array object is created, its size cannot be changed although an array variable can be made to refer to another array object of a different size without problem. The length of an array object can be found by referring to its length field, so a.length is the length of the array referred to by a. The length field may not be assigned a new value, however.

Arrays are indexable and mutable. An array created using a = new X[exp1]; consists of what can be considered a number of variables of type X called a[0], a[1], a[2] and so on up to a indexed by one less than the value of exp1 when it was evaluated to create the array. Counting of array elements always starts at 0 in Java. These variables can be assigned values (hence arrays are mutable), or used in expressions in just the same way as any other variables of type X. But the whole of the object can be passed by reference as an argument to a method where the signature indicates the argument is of type X[].

The indexable nature of arrays comes about because we can refer to a[exp2], where exp2 is any expression that evaluates to an integer. Since exp2 may have different values each time it is evaluated, it may be used as a varying index to different parts of the array. If exp2 evaluates to a value less than 0 or equal to or greater than exp1 when the array was created, an ArrayIndexOutOfBoundsException will be thrown.

We looked also at three other things, static final variables, command line arguments and reading from files.

A static variable is a variable of which there is just one copy in a class (a non-static variable declared in a class has a separate copy for every object of that class), while a final variable may never have its value changed during the execution of a program. Declaring a variable as both static and final and giving it a value is a way of giving a name to that value which can be used as a constant in the program. It is good programming practice, since it makes your program easier to understand and modify, to define static final values and then use their names rather than use numeric literals in methods.

The main method used when a Java program starts has an argument of type String[], by convention named args. If when you run a Java program from Unix you follow the words java Filename (where Filename refers to any .class file) with some further words, args[0] will be set to the first of these words, args[1] to the second, and so on, with the length of args equal to the number of words. These are the command line arguments.

The expression new BufferedReader(new FileReader(string)) creates a BufferedReader object attached to the Unix file named in the expression (which must evaluate to a string) string. Reading from this BufferedReader, for example using its readLine method will read from that file rather than from the command window as we have used BufferedReader for so far. If no file exists with the name given by string a FileNotFoundException is thrown.

Additional work

Week 13: 17th-18th January 2001

Continued talking about arrays. Two different methods to sort arrays of integers were discussed. Note these were given for their conceptual simplicity and ease of representation in Java, not as ideal sorting methods (they are in fact rather inefficient). Sorting is something that is covered in much more detail in the Introduction to Algorithms course. The lecture material on sorting closely followed the Numbers Part 2 notes available in the local resources. The main difference between the two methods was that one involved "sort in place", that is changing the ordering of the contents of the array that was passed to it as its argument, while the other involved creating a new array of integers while leaving the initial array unchanged. This is just one case of a more general distinction between destructive and constructive methods operating on objects.

A destructive method works by actually changing the data of an object which is passed to it as an argument. It is termed "destructive" because it destroys the initial form of the object by overwriting it. A constructive method, however, creates a new object which is equivalent to the old object with the desired changes to it. It leaves the old object unchanged and still referred to by the reference that was given as an argument to the method. It is important to remember when using constructive methods that while we will often talk or write about them using language which would seem to imply changing objects we actually mean by this creating a new object while leaving the old one unchanged.

We also covered briefly how Java could give the equivalent of higher order functions, which those who have taken the course Functional Programming will have encountered in the Miranda programming language. The idea is that you can have arguments to methods (or "functions" as they are called in Miranda) which are other functions. In Java you can't pass a method as an argument, but you can pass an object which provides that method, this can be done through interfaces which we discussed in week 11

For example, if we want to pass a function which takes an integer and returns an integer to a method, we can do so by writing an interface which defines a type of object which has such a function. We could call the interface type anything we liked, but IntToInt would be a sensible name for it, so:

interface IntToInt
{
 public int func(int n);
}
just that in a file called IntToInt.java would do the trick. We could then have classes which implement IntToInt by providing a method with the signature public int func(int n) and the code doing whatever it is we want to pass as an argument. For example,
class Cube implements IntToInt
{
 public int func(int n)
 {
  return n*n*n;
 }
} 
means that if objects of type Cube are passed as arguments to methods with a parameter named obj of type IntToInt, then obj.func(n) will return the cube of n.

Additional work

Week 14: 24th-25th January 2001

Went in detail through a set of examples (the "drinks machine" examples) which didn't introduce many new concepts but covered again in one example much of what we have done previously.

First we considered an interface file for drinks machines. This is a way of defining a type of object in terms of what you can do with objects of that type. Operations we would want from a drinks machine were listed in the interface as Java method signatures representing those operations.

An interface type is an abstract type. You can't actually have objects directly of that type, you can only have objects of other types that implement that type. Next we looked at a number of different types that implemented the type DrinksMachine given by the drinks machine interface. To implement that type they had to have a full method for each of the signatures listed in that interface. But they could also have extra methods.

The important thing about interfaces is that they give us generalised types. A variable or method argument of the type DrinksMachine could be set to refer to an object of any of the types (some of those we gave were SimpleDrinksMachine, DrinksMachineA, DrinksMachineB) which implement the interface DrinksMachine. So if we want a general method to compare two drinks machines to see which is the cheapest, we can just write one with two DrinksMachine parameters, rather than one with two DrinksMachineA parameters to compare two objects of type DrinksMachineA, one with two DrinksMachineB parameters to compare two objects of type DrinksMachineB, one with a DrinksMachineA parameter and a DrinksMachineB parameter to compare a DrinksMachineA object and a DrinksMachineB object, and so on.

So in general this gives us the idea, crucial to object-oriented programming, of overlapping types. An object can be of one type, but also of another type. An object of type DrinksMachineA for example, is also of type DrinksMachine. We can say that DrinksMachineA is a subtype of DrinksMachine, since the collection of objects which are of type DrinksMachineA is a subset of the collection of objects which are of type DrinksMachine. Or, to put it another way, DrinksMachine is a more general type than DrinksMachineA.

We can assign a more specific type to a more general variable. So if we have a variable declared as DrinksMachine dm, and a variable declared as DrinksMachineA dma, we can have the statement dm=dma. But we cannot assign from more general to more specific, as in dma=dm, since we can't be sure the more general variable refers to an object of the appropriate subtype - in this case dm could, for example, have been set to refer to an object of type DrinksMachineB. To assign from more general to more specific we need to use type casting, in this case it would be dma=(DrinksMachineA)dm. Note that if this were executed at a time when dm happened to refer to an object that was not of type DrinksMachineA, an exception of type ClassCastException would be thrown. If you want to check whether a particular object expression can be type cast to a more specific type, you can do by using the instanceof operator. For any expression e and type name d, the boolean expression e instanceof d evaluates to true if e evaluates to an object that can be type cast to type d, and to false otherwise.

A method can only be called if attached to a variable (or other expression) of a type which contains that method (in the case of interfaces as a signature rather than full method) or which inherits it. For example, the zero-argument method pressChange is defined in DrinksMachineB but not given in the interface DrinksMachine. So it would result in a compiler error to call dm.pressChange() where dm is declared of type DrinksMachine, even in circumstances where it can be shown dm must refer to an object of type DrinksmachineB. In this case, you need to use typecasting to call the method, either anonymously as in ((DrinksMachineB) dm).pressChange() or by creating a named reference to the object of the appropriate type, as in:

DrinksMachineB dmb = (DrinksMachineB) dm;
dmb.pressChange();

Additional work

Week 15: 31st January - 1st February 2001

Mainly revision, in particular we went over some of the questions on the semester 2 test paper of the previous academic year.

First, however, was a reminder of the importance of taking a structured view of methods. A statement of the form if(test) { statements } else { statements } or while(test) { statements } is a single statement which contains substatements, and you should think of it this way. It's important to lay out your code in a way that makes this structure clear (some notes on this were given previously here) even though the layout means nothing to the Java compiler. It's good practice when writing code in a text editor actually to write

while(test
   {
   }
and then fill in the bit between the curly brackets because as an opening curly bracket is always matched with a closing one you might as well make sure you put in the closing one right away rather than have to remember to do so later.

The last question on the test was covered first, it was about spotting errors in a piece of code. The errors were those commonly found from novice Java programmers: forgetting to declare variables, using variables outside their scope, forgetting that Java is case sensitive (i.e. a word with a capital letter is completely different from one with the same letters but a small letter replacing the capital), forgetting that readLine called on a BufferedReader returns a string that must be converted if you want to read an integer, not realising that a semicolon at the end of a for-loop header means the loop has no body, forgetting matching brackets, using constructs from other languages (e.g. supposing that System.out.println can take multiple arguments because Pascal's writeln can).

Next we covered one of the array questions. Arrays are a fundamental concept in programming, introducing the idea of indexing, that is a sub-part of a structure can be referred to by a name for the structure followed by an index (in Java like many languages the index is enclosed by square brackets), where the index may contain variables so the sub-part referred to changes as the program executes. Arrays are mutable in Java, so you can change the value of their subparts (in contrast, for example, to strings where you can access the component characters but not change then so strings are immutable).

Finally we covered the first question which was on objects with a particular emphasis on inheritance. A few new terms were introduced. An IS-A relationship between classes means one class extends another. So if we have, for example, class Dragon extends Monster, we can say "A Dragon IS-A Monster", because an object of type Dragon can be considered a specialised form of an object of type Monster. Two classes are said to be in a HAS-A relationship if one class has a field within it whose type is of the other class. In the example given, one of the fields of class Hero was of type Weapon so we could say "A Hero HAS-A weapon".

One question brought up the topic of dynamic binding, which is also referred to as late binding. We can have a variable of one type refer to an object of one of its subtypes, for example a variable of type Monster could refer to an object of type Dragon. In that case, if the subtype introduces a variant of a method (overloading), when that method is called on the variable, which actual method is used, the one in the class of the variable or the one in the class of the object? The answer in Java is the one of the type of the object, Dragon in this case. In some other programming languages it could be the other way round (known as "static binding" or "early binding"). The names here come from whether the actual method used is chosen when the program is compiled (early on, or fixed in compilation i.e. "static"), or when it is run. You may only know what is the actual type of an object a variable of a more general type refers to when the code is run, hence the idea of making the decision on which method to use as late as possible (when the program is run i.e. "dynamically").

Additional work

Week 16: 7th-8th February 2001

The lecture time on 7th February was given over to a test. You can get a copy of the test paper (in postscript form) here. A copy with the answers filled in is available here.

The lecture on 8th February continued going over questions from the semester 2 test of the previous academic year. Please note this test was sat on 1st March 2000. Therefore, you are expected to reach the standard of being able to answer a test of this sort by 1st March 2001.

You can find programs that give answers to this test in the directory /import/teaching/BSc/1st/ItP/test. There are modified forms of the "monster" classes there which include the answers to question 4 of part A of the test, a file called PartA.java, which gives the answers to question 2 of part A by actually running the code in that question, a file called PartB.java which similarly gives the answers to question 1 of part B, and a file called Averages.java which is the code of part 3 of part B corrected to remove the errors.

Additional work

Week 17: 14th-15th February 2001

In the first lecture we started covering a series of examples, the code for which can be found in the directory /import/teaching/BSc/1st/ItP/banks. In this directory there are a number of files all implementing the basic idea of a program in which a collection of bank accounts can be manipulated: new accounts can be created, old accounts can be deleted, and money can be deposited or withdrawn from existing accounts.

There is a front-end file which gives a text interface to the system and the main method which is where program execution starts. In the example we looked at, this was in the file UseBank1.java. There is a file which contains the collection of account records, in the example we looked at it is called BankA.java and the records are stored in an array. The actual accounts are of types we looked at in week 10, with a basic account having a subtype deposit account from which withdrawals are limited. We used the AccountB type in which a withdrawal that fails is signalled by an exception being thrown.

However, the bank stores an array not of AccountB objects but of AccountRecord objects, which have an AccountB field as well as fields for the account holder's name, account number and a security number. It could be asked why the additional information was not given by making class AccountRecord extend class AccountB. Conceptually this would be wrong because we don't want to think of an AccountRecord as being a kind of AccountB object, rather it HAS-A AccountB object. Practically, we couldn't do it because we want an AccountRecord object to add extra information to something which could be a DepositAccountB object, but it couldn't if AccountRecord were a direct subtype of AccountB, while an AccountRecord couldn't refer to an ordinary AccountB if it were a subtype of AccountB. A class which adds some extra information to some other type by including an object of that type as one of its fields rather than extending the type is known as a wrapper class.

In the second lecture we went over the questions from the previous week's test. The following points were made:

Additional work

Week 18: 21st-22nd February 2001

Continued covering the series of example which can be found in the directory /import/teaching/BSc/1st/ItP/banks. The examples illustrate the important principle of information hiding. Although the class BankA (and BankB, BankC and BankD) stores the collection of AccountRecord objects in an array, there is nothing in class UseBank1 (nor UseBank2 which uses BankB and so on) which makes use of this. Because the array is protected inside the BankA object, only this object can manipulate it. Other objects can manipulate it only indirectly by calling those methods which BankA makes public. This means the chance of bugs developing because of unexpected interactions between a BankA object and other code are limited because no other code can interfere with BankA's array. It means the author of the code for BankA can safely write that code knowing the structure of the array will not be altered by any outside code. It also means that should a decisions be made to change the way the data is represented, say from an array to some other form of collection, it is not necessary to search through the code for UseBank1 or anything else to make changes, as the only changes that would have to be made are within class BankA.

We noted that if we have a collection of objects which we want to place in some order, there may be more than one criterion for ordering the objects. A collection of AccountRecord objects, for instance, could be sorted in order of the account numbers, in order of the balance in the accounts, or in alphabetical order of the names of the account holders. One could imagine more complex objects with more possible ways of ordering them. The class BankB gave separate methods for sorting on each possible criterion, but this was unsatisfactory. Why have large amounts of code differing only in one small part where objects are compared?

The solution was to generalise the sort method by having a parameter passed in which gave the criterion used for ordering objects. This parameter had to be of a type which had a single method which took two AccountRecord objects and gave a boolean. Hence it was defined by the interface:

interface AccountComparer
{
 public boolean before(AccountRecord accr1, AccountRecord accr2);
}
Calling the before method on the AccountComparer object passed as a parameter would compare two AccountRecord objects by the criterion of some subclass of the type AccountComparer. A subclass would provide actual code for the before method, and any AccountComparer object must also be a member of a subclass since you cannot have an object which is a member of an interface class but not one of the classes which implements it.

But we could go even further than this and write a method which is generalised to sort arrays of any object. The code for this method is found in class GenArraySorter. The reason this can be done is that Java provides a type Object which is a superclass of all objects. So a general method which sorts an array of type Object can sort any array of any objects, though it needs to have passed into it a parameter indicating how it is to compare objects. That parameter will be of the type defined by the interface:

interface GenComparer
{
 public boolean before(Object obj1, Object obj2);
}
Any class implementing this type must have a method called before with a header that indicates it takes two arguments of type Object, but it could use typecasting to compare objects of a more specific type, for example:
class GenAccountCompByName implements GenComparer
{

 public boolean before(Object accr1,Object accr2)
 {
  String name1=((AccountRecord)accr1).getName(), 
         name2=((AccountRecord)accr2).getName();
  return name1.compareTo(name2)<0;
 }
}

We noted that while a variable (or array cell) of type Object could be set to refer to any object, it could not be made to contain a primitive value such as an int. To get round this, Java provides object types which match the primitive types. These are called primitive wrapper classes. For example, the type int is matched with the wrapper type Integer. Full details of the methods these types provide can be found in the Java on-line documentation, for example here is the documentation for class Integer. An int can be converted to an Integer using the constructor for Integer, so:

Integer N = new Integer(m);
defines a new variable of type Integer and sets it to refer to an object which is the Integer equivalent of the int value in int variable m. The reverse conversion is done by the method intValue, as in:
int m = N.intValue();
The primitive wrapper classes also provide general methods for common operations associated with values of their type and matching primitive type. We are already familiar with the static method parseInt from class Integer as we have used Integer.parseInt(str) as the way to convert a String to the int value it represents. But perhaps we did not realise till now that it was actually a call to a method from a class rather than just an arbitrary bit of Java.

Additional work

Week 19: 28th February - 1st March 2001

Covered briefly binary search as a more efficient way of locating information in an array given a key (such as a bank account from a collection of bank accounts using the account number as a key), providing the information is stored ordered by the value of that key. This is the sort of thing those taking the Introduction to Algorithms course will have seen more of there. Because of that separate course, there won't be any detailed discussion of algorithms in Introduction to Programming. However it is important for everyone taking it (including those not also taking the algorithms course) to be aware there are often several ways of doing something and one way may be more efficient than another. The principle of information hiding discussed last week enables us to make changes, should we discover a better algorithm, without having to massively disrupt a program. In the banks example, searching for a bank account given an account number is done in just one method in just one class, called whenever such a search is needed. That means we only have to change the body of that method if we want to change the algorithm it uses for searching.

We noted also that this was a case where we would want to declare a field as private rather than protected. A private field in a class can't be accessed even by code in clases which extend that class, whereas protected fields can't be accessed by outside classes but can by subclasses. In this case since the binary search algorithm relies on the data in the array being ordered, the class which employs it (BankABinarySearch) can't afford to let subclasses have access to the array as they may disrupt its ordered quality.

The main topic covered, however, was linked lists. Again the principle of information hiding was valuable. The class BankE represented the collection of bank account records using a linked list rather than an array. However, as all the code which actually manipulates the representation is inside the classes BankA, and so on, we can introduce the completely new class BankE with almost no disruption to the rest of the bank program, so long as BankE provides methods with the same signature and outward behaviour as BankA. All we had to do was change the line which created a BankA object to one which created a BankE object.

A linked data structure works by having objects with at least one field of the same type as the object. This enables objects to be chained together with this recursive field as the link. The chains won't necessarily go on for ever because the field can be set to the special value null which means "does not refer to any object" (also, as you saw in the lab exercise, you can also create chains that link back on themselves making circular structures).

The linked lists we saw had fields that were not private or protected, hence they could be altered by any other code. This could be dangerous since without controlled access it's easy for unexpected interactions to take place between different methods altering the structures. However, in the case of BankE this danger was avoided by making the class for linked lists an inner class. An inner class is a class whose complete code is given inside another class. It can be declared as public, private or protected, just like a method or a field in a class. If the class is private or protected no variable of its type can be declared outside the class that encloses it (and its subclasses for protected). Therefore there is no access to the fields of object of the inner class except within its enclosing class. Inner classes may also be declared as static or not. If an inner class needs to refer to fields of an object of the enclosing class it can't be static, and the class can be thought of as having a separate copy attached to each object of its enclosing class. But if there is no reference to fields of the enclosing class, it's more efficient to make the inner class static, making just one copy of the class to the enclosing class (just like static methods and fields). In this course we will only consider static inner classes. Note that some authors (e.g. Barnes) use the term nested class to mean any class declared inside another class, and restrict the term inner class to mean only non-static classes inside other classes.

Additional work

Week 20: 7th-8th March 2001

This week we covered sorting linked lists, then recursion. The class BankF extends the class BankE by adding to it methods which sort the list of bank account records. Sorting is done by setting up a new list, initially empty, then going through the bank accounts from the list of the BankF object inserting them in order into the new list. The object's list is then replaced by the new list. There is a private method to carry out the inserting. Class BankF has separate sorting methods (with accompanying inserting methods) for the different ways in which bank accounts may be ordered. Class BankG shows sorting in the same way but using a generalised method, as we saw previously with sorting arrays, in which the way in which bank accounts are compared during sorting is given by a separate object passed as a parameter. It should be noted that the sorting algorithm used here is given only for illustration, and is not an efficient way of sorting a list.

Class BankGRec provides the same functionality as code class BankG, that is it provides methods of the same name which appear to perform the same actions. The only difference is what happens internally, as BankGRec uses recursion for listing the bank accounts and sorting them. A recursive method is one that can call itself. The methods we saw previously for manipulating linked lists were iterative, which means they used loops. An iterative way of solving a list problem generally involves setting a variable (referred to as a pointer) to refer to the first element of the list then moving it down the list. A recursive method with a list as an argument will generally call itself with the tail of the list as its argument.

How can a method "call itself"? What we should really think of it as is solving a problem by solving a smaller version of the same problem. Eventually we will reduce the problem to a point so trivial we can solve it instantly. So one way to sort a list is to sort the list consisting of all but its first element, and then insert that first element into it in order. That is, we solve the problem of sorting a list in a way that involves the smaller problem of sorting a list one smaller in size. Eventually we will reduce the problem to the trivial one of sorting an empty list, which of course gives the empty list.

In recursive methods, the trivial case is referred to as the base case. It is always necessary for a recursive method to have a base case and for any recursive call to give a version of the problem closer to the base case, otherwise recursion will never come to an end - just like an infinite loop. A method may have more than one base case, for example when dealing with inserting an item into an ordered list, one base case is dealing with the problem of inserting an item into the empty list, the other is dealing with inserting it into the list whose first element is greater than it in the ordering being used.

We noted that the recursive methods we used for list handling were constructive, that is they solved their problem by constructing a new list which represented the desired change to the old list but without actually changing the old list. This contrasted with the destructive iterative methods we used previously which actually changed the way the pointers linked together in the list. In our bank examples, linked lists were protected from interference by being enclosed inside another class which held a single linked list and had the class for the linked list inside it as an inner class which outside classes could not access. However, if the linked list class were a separate class, the possibility of several linked list variables and fields referring to the same structure exists, so a change meant to affect one could accidentally affect another. Using constructive methods means such interference does not happen. Recursion applies naturally to linked lists, because linked lists are a recursive data structure.

Additional work

Week 21: 14th-15th March 2001

We had a brief diversion into the Java keyword this. If you want to refer to the object a method is attached to inside the code for that method, you can do so, that is what this means. So if we have some object referred to by obj and some method called on it obj.someMethod(...) (where the ... is some arguments), then when the call to someMethod is executed, inside its code this is a reference to the object that was referenced by obj when the call was made.

The main topic covered, however, was the idea of an Abstract Data Type (often abbreviated to ADT). This is an object defined not by how it's represented in the programming language used, but by the operations that may be done on it. In Java this means the type can be given by an interface which lists the operations as method signatures.

We only had time to look at one simple ADT, a simple type we called List, which is designed to be like the lists those who took the Functional Programming course will have encountered. Once we have this type we can write programs in a functional style in Java. A List is an ordered collection of elements. The operation head gives the first element, the operation tail gives the list which is all of the original list except the first element, the operation cons takes a list element as an argument and returns a list whose head is that element and whose tail is the list the call to cons was made on. There is also a test, isEmpty, which tests whether a list is empty.

The linked lists we saw in week 19 worked similarly to the lists we saw this week, but in their case their head and tail was given by a public field, so if ll was a linked list, then ll.first was its head, and ll.next was its tail. The problem with this is that as they are fields they can occur on the left-hand side of assignments. ll.first=x changes the head of the list referred to by ll to x, but due to aliasing if another linked list variable refers to the same list, its head will also be changed by that assignment.

Contrast this with the List type, where if al is a List, then al.head() is its head, but as this is a method call it can't occur on the left-hand side of an assignment, al.head()=x is not valid Java. You could get the effect of changing the head of al to x by al=al.tail().cons(x), but this constructs a new List object, and does not affect any other variable that refers to the List object al referred to before this assignment.

We noted that the interface List could be implemented in more than one way. An obvious way is as a linked list, with the linked list cell type as a private inner class thus protecting it from outside interference. But to demonstrate that the type List needn't have anything to do with linked lists, another implementation was given where a List is represented by a pair: an array storing the list elements, and an integer giving the number of elements from that array that are in the list. The implementation stored the list "backwards" in the array, so the element that was the head of the list was stored in the highest indexed cell of the array that was in use.

The class BankH showed the bank example we have been using since week 17, this time with the collection of bank accounts stored using the separate class List. The methods to delete account records and to retrieve account records from the list given their account number and pin employed recursion, which is natural with this recursive data type. The class BankI extended BankH by adding methods to list and sort the collection of account records. Sorting employed a separate class GenListSorter which could sort any List so long as it was given also an argument which told it how to compare the objects in the List. The class GenListQSorter showed sorting using the more efficient quick sort applied to lists (those taking the Introduction to Algorithms course will have seen that way of sorting). An interesting point in GenListQSorter is that the partition method which is meant to return two lists returns a pair of lists given by an inner class (ListPair) defined just for that purpose. This shows how to get round the problem that a Java method can only return one value.

Additional work

Week 22: 21st-22nd March 2001

The first lecture was given over to the final term-time test for the course. You can obtain a fresh copy of the test paper here. A copy with model answers is available here.

In the second lecture we started going over the year 2000 exam paper. Questions 1 and 2 from part A were covered in detail, including discussion of common mistakes found in the scripts from last year's students. Key point raised were:

Additional work

Week 23: 28th-29th March 2001

In the first lecture, we continued going over last year's exam paper, discussing in detail questions 3 and 4 of part A.

Question 3 reminded us about parameters to methods. Parameters are things that can be varied each time the method is called. When a method is defined, its parameters and their types are listed in the type signature, following the name of the method and the ( symbol, separated by commas if there are more than one, and ended by the ) symbol. A call to that method has the same number of arguments listed between the ( and the ) of the call, but does not have type names given with the arguments. The arguments are matched up against the parameters in the method signature, and they must be of the same type as that given for the parameter they match, or a subtype of it. The parameters can be considered as separate variables which exist for the duration of the execution of the code of the method and which are initialised to the same value as their matching argument in the method call.

Question 3 reminded us that a standard pattern for doing something a certain number of times is to use the code for(int i=0; i<n; i++) do something where n is the number of times it needs to be done. The variable i exists only while the for loop is being executed. Sometimes (although not in question 3) what is done in do something will depend on the value of i.

Question 4 was on cells and pointers. It was noted that although this question used field names head and tail for the fields in the cells of a linked list referring to the first element and the reference to the rest of the list, that should not be confused with the abstract data type List, which is what question 4 of part B of the paper was about. In the abstract data type, the head and tail of a list are given by methods, not fields. You can change a cells-and-pointers list by assigning a value to its fields, for example ls.head='x' will change the head of the list of characters represented by ls to the character 'x', but you can't change an abstract data type list in this way. A statement like ls.head()='x' is not valid Java, because ls.head() is a method call, not a piece of store that can be assigned a value.

The questionnaires for the course were given out in this lecture. Would all students who were absent from the lecture please ask at the department office for a copy of the Introduction to Programming questionnaire which they can fill in to give their views on the course. It is important to get the views of those who haven't been attending lecures as well as those who have. Your anonymity in filling in the questionnaire will be respected.

The second lecture in this week went through questions 1, 2 and 3 of the third term-time test for the course. A commentary on this test and common problems found in answers to it has now been made.

Comments on test 3.
Additional work

Week 24: 4th-5th April 2001

We continued going over last year's exam paper, covering the rest of section A, and also part a of question 4 of section B. This little bit bit of section B was covered in order to give some more coverage of using the abstract data type form of lists we only briefly covered in week 21.

As we did not get time to cover any more of section B of last year's exam paper, I have made some written notes on part B available, which include complete answers to the questions.

Answers (with explanations) to part B of 2000 exam paper
Additional work


Matthew Huntbach
Last modified: 28 September 2001