So, please don't look at these answers until you've looked at last
year's exam paper
(
here is another link to it) and tried to answer each of the part B
questions on your own. However, as answers without explanation aren't
of much use, I've also added explanation. As it happened, all the part
B questions last year were coding questions, so the answers below are the
material in Courier font, while the rest is explanation.
class Dictionary
{
private static class Entry
{
String word1,word2;
}
Entry [] entries;
int numEntries;
static int MAXENTRIES=10000;
public Dictionary()
{
numEntries=0;
entries = new Entry[MAXENTRIES];
}
Note this is just the start of class Dictionary. The class
would also have to include the methods mentioned in part b.
The question specifically said that marks are assigned for correctness rather than efficiency. You ought to realise that storing the entries in the dictionary in an array, and not putting them in any particular order, would be a very bad way of doing it if you were writing a serious program to do this job. That is because of the amount of time it would take on average to look up a definition. However, an answer using this representation is easy to write quickly, and the question makes clear that's all that's expected.
Note the use of an inner class called Entry to store
the entry for an individual word, consisting of just a pair of strings
giving the word in the two different languages. Also the question
specifically stated that the dictionary would have no more than 10,000
entries, so an array of just this size is created to store them. That
does not mean the dictionary will always have exactly 10,000 entries, it is
one of those cases of an array being created of the maximum possible
size needed, then a separate count being held (here in the field called
numEntries) of how much of the array is actually in use.
public String lookup(String word)
{
for(int i=0;i<numEntries;i++)
if(entries[i].word1.equals(word))
return entries[i].word2;
return null;
}
Just goes through the array one entry at a time, until one is found whose
word1 field is equal to the string that was given as an
argument to the method, then the matching word in the entry's
word2 field is returned as the result. Note that the
question did not say how to deal with the case where the word given as
an argument is not found in the dictionary, so any sensible way of
handling it would do, in this case returning null.
The line that returns null is only reached if every
time round the loop no cell of the array entries is found
where entries[i].word1.equals(word) is true.
If such a cell is found, the statement return entries[i].word2
is executed and the method terminates returning the appropriate word
and never reaching the line which returns null.
Note that entries and numEntries are the
fields we defined as being in the class Dictionary in
part a. When the method lookup is called,
entries and numEntries in its code will
refer to the entries and numEntries fields
of the Dictionary object the method call is attached to.
public void add(String w1,String w2)
{
Entry temp = new Entry();
temp.word1=w1;
temp.word2=w2;
entries[numEntries++] = temp;
}
Nothing fancy - the new entry is put in the next available free cell in the
array, and the count of the number of entries increased by one.
public Dictionary join(Dictionary d1)
{
Dictionary d2 = new Dictionary();
for(int i=0;i<numEntries;i++)
{
String word = d1.lookup(entries[i].word2);
if(word!=null)
d2.add(entries[i].word1,word);
}
return d2;
}
This might require a little more thought, but the answer should be
fairly obvious once you've thought about it. To make it a little more
concrete, if you had an English to French dictionary and a French to
Chinese dictionary, could you create an English to Chinese dictionary?
Yes - you would go through the English to French dictionary, then for each
French word equivalent to an English word in that dictionary you'd find the
equivalent Chinese word in the French to Chinese dictionary and make a new
entry in your English to Chinese dictionary (except if there is no
equivalent Chinese word to the French word). This is precisely what the
code does above - note it makes use of the methods defined in the previous
two parts. You quite often will find you can get a solution to one part of
a question by using methods given in another, which will both save time
and give a more elegant solution.
Of course, the fact that one natural languages won't have precise equivalents to every word in another means in reality you couldn't quite make an A-C dictionary from an A-B and a B-C dictionary in this way. But this question is a programming exercise, not a serious attempt to discuss natural language.
interface StringTransformer
{
String transform(String aPhrase);
}
That ought to have been a very easy five marks gained, so long as you
understand the concept of Java interfaces as a way of defining a type
in terms of the methods that can be called on objects of that type.
static void map(String[] a, StringTransformer change)
{
for(int i=0; i<a.length; i++)
a[i] = change.transform(a[i]);
}
An excellent example of how Java interfaces can be used to give an
effect very close to the higher-order functions of functional
programming. Note the question talks of "changing" the array,
which ought to make it obvious that it's a destructive method,
so it has void as its return type, and actually
changes the content of the array passed as a parameter. As the
question makes no mention of the method being attached to any object,
all the data it requires is given as its arguments, and the method
is static. We do not need to know what the object called change
when it is an argument to this method does. All we know is that as it is
of type StringTransformer, it must be possible to call
the method called transform on it, which takes a string
an returns a string.
static String[] cmap(String[] a, StringTransformer change)
{
String [] b = new String[a.length];
for(int i=0; i<a.length; i++)
b[i] = change.transform(a[i]);
return b;
}
Here the question specifically asks for the effect to be constructive
rather than destructive. So a new array of strings is created,
and set to the result of applying the transform
method from the object change to every string in the
array given as an argument.
class Multiple implements StringTransformer
{
protected int times;
public Multiple(int n)
{
times=n;
}
public String transform(String aPhrase)
{
String s="";
for(int i = 0; i<times; i++)
s+=aPhrase;
return s;
}
}
Any implementation of StringTransformer must have the
method transform in it. In this case, objects of type
Multiple must have their own field giving the number
of times a string is multiplied when given as the argument to their
transform method. The class needs a constructor which
sets the value of this field. Objects of class Multiple
are immutable because there is nothing which can change the value
of this field once it is set when they are constructed.
class ChangingMultiple extends Multiple
{
public ChangingMultiple(int n)
{
super(n);
}
public void changeMultiplier(int n)
{
times = n;
}
}
Here is a subclass of Multiple whose objects are mutable.
This subclass will inherit the method transform from
class Multiple, along with the field times,
but the extra method called changeMultiplier enables the
times field of a ChangingMultiple object to be
changed.
import java.util.*;
import java.io.*;
class Process
{
public static void main(String[] args)
{
BufferedReader in=null;
if(args.length!=2)
{
System.out.print("Must have two command line ");
System.out.println("arguments");
System.exit(1);
}
try {
in = FMeths.open(args[0]);
}
catch(FileNotFoundException e)
{
System.out.println("Unable to open file "+args[0]);
System.exit(2);
}
int numQuestions=0;
try {
numQuestions = Integer.parseInt(args[1]);
}
catch(NumberFormatException e)
{
System.out.print("Second command line argument ");
System.out.println("must be an integer");
System.exit(3);
}
int [] marksSum = new int[numQuestions];
for(int i=0; i<numQuestions; i++)
marksSum[i]=0;
int linecount=0;
for(;;)
{
String line1="",line2="";
try {
line1 = in.readLine();
}
catch(IOException e)
{
break;
}
linecount++;
try {
line2 = in.readLine();
}
catch(IOException e)
{
System.out.print("File must have even number");
System.out.println(" of lines");
System.exit(4);
}
linecount++;
StringTokenizer tokens = new StringTokenizer(line2);
int i=0;
try {
for(;tokens.hasMoreTokens();i++)
marksSum[i]+=
Integer.parseInt(tokens.nextToken());
}
catch(ArrayIndexOutOfBoundsException e)
{
System.out.print("Line "+linecount);
System.out.println(" has too many numbers");
System.exit(5);
}
catch(NumberFormatException e)
{
System.out.print("Line "+linecount);
System.out.println(" has non-integer data");
System.exit(6);
}
if(i<numQuestions)
{
System.out.print("Line "+linecount);
System.out.println(" has not enough numbers");
}
}
for(int i=0; i<numQuestions; i++)
{
System.out.print("Question "+(i+1)+": average ");
System.out.print(marksSum[i]*2/linecount+".");
int decimal = (marksSum[i]*200/linecount)%100;
if(decimal==0)
System.out.println("00");
else if(decimal<10)
System.out.println("0"+decimal);
else
System.out.println(decimal);
}
}
}
Note this is the only place in the whole exam where you are asked
to write a whole program. Nowehere else but this question should the line
public static void main(String[] args)appear as part of any answer.
The answer to the question is fairly straightforward if somewhat long and tedious. In fact this question is something of a concession for those who have significant pre-university proramming experience, but haven't really taken into account the new object-oriented approach to programming covered in the Introduction to Programming course.
One thing it does ask for which might trip up someone who hadn't
paid attention to any of the classes, is for arguments to the program
to be given as command line arguments. This was covered in the course
(week 12),
but is one of those details people may have forgotten by exam time.
It also requires a knowledge of string tokenizers (covered in
week 7 to break up lines of text into individual words, and
how to convert a string to an integer using Integer.parseInt
covered in week 8
List are generally best solved using recursion. If you
can learn to think recursively, answering these questions can be
relatively easy. All the answers below use recursion. It would be
possible to write iterative solutions, but they would be more complex.
It is very important with this sort of question to note the
difference between a linked list (the topic of question 4 of section A
of the 2000 paper) and an abstract data type list. With a linked list,
the head and tail of a list are provided by public fields.
So with a linked list L as given in question 4 of section A,
you could change the list's head to the character 'm' for
example by the statement L.head='m'.
But with a list given as an abstract data type, as in question 4 of
section B you can't do that. The head and tail of the list are
given by methods not fields. If L is of the
type List as defined in question 4 of section B, you can't
change the head of the list by the statement L.head()='m'
because that statement doesn't even make any sense. L.head()
is not a piece of computer store, it's a call to a method, so it doesn't
make sense to attempt to assign something to it.
The abstract data type list is often implemented using a linked list, but as all we have is the interface providing its methods we cannot know that. It is very important when answering questions about lists to make sure you understand the difference between the abstract data type list and the concrete data structure linked list, and not to answer questions about one of these as if it were asking about the other.
public static List replace(List L, char ch1,char ch2)
{
if(L.isempty())
return MyList.empty();
else
{
char h=L.head();
List t=replace(L.tail(),ch1,ch2);
if(ch1==h)
return t.cons(ch2);
else
return t.cons(h);
}
}
Note that the question does not ask you to define the methods
head, tail and so on. Nor does it ask you to
use the class MyList for anything other than obtaining a
new List object representing the empty list. The usual
convention that variable names should begin with small letters and
class names with capital letters is broken here simply because using
small l for a list variable/argument can look confusingly like 1 (the
character for the number one). There is nothing in Java that says
variables should not begin with capital letters, but it just helps us
understand Java programs a little bit if they never do, and classes
always do. For example, if we see a method attached to something beginning
with a capital letter, we would then know that something must be a class
name, so the method must be a static method in that class. You should
observe these conventions in writing Java programs unless (as here) there
is a good reason not to.
public static int position(List L,char ch)
{
if(L.isempty())
return 0;
else if(L.head()==ch)
return 1;
else
{
int p = position(L.tail(),ch);
if(p==0)
return 0;
else
return p+1;
}
}
You need to be a little bit careful with this question to make sure it
really does return 0 if the character does not occur in the list. You
might think that if a character occurs in the ith
position in the tail of a list, it must then occur in the
i+1th position in the whole list. That is the
correct recursive way of thinking that helps you solve this problem.
But in this case, you need to be aware of the case that if the
recursive call on the tail of the list returns 0, that means the
character does not occur in the tail of the list, so assuming it
is not the head character of the list, the whole method must return 0
to indicate the character does not occur in the list. Returning
0+1, i.e. 1 because the recursive call returns 0, would suggest wrongly
that the character is at the head of the list.
public static int lastPosition(List L,char ch)
{
if(L.isempty())
return 0;
else
{
int p = lastPosition(L.tail(),ch);
if(p!=0)
return p+1;
else if(L.head()==ch)
return 1;
else
return 0;
}
Note the fairly subtle difference between the answer to this part and
the answer to part b. In the case of part b, if the character whose
position we're looking for is at the head of the list argument, then
we return 1, as the character is in the first position and we needn't
consider later positions. Here we look for a later occurrence first, and
return 1 if the character is at the head of the list and isn't also found
later in the list.
public static int charBetween(List L,char ch1,char ch2)
{
if(L.isempty())
return -1 ;
else if(L.head()==ch1)
return(position(L.tail(),ch2)-1);
else
return charBetween(L.tail(),ch1,ch2);
}
Here, although the questions did not specifically mention that you
could use one of the previous answers, the question becomes much
easier to answer if you realise that in fact part of the solution
involves doing something you've already done. Thinking recursively,
the number of characters between two particular characters in a list
is the same as the number between those two characters in the tail of
the list if the first character in the list is not the first delimiting
character. Otherwise, it is one less than the position of the second
delimiting character in the tail of the list.
Note this question did not tell you how to deal with the case where one or the other of the delimiting characters does not occur in the list. You couldn't return 0 in this case, as 0 would be returned when the two delimiting characters are next to each other in the list. The answer given returns -1 when one or other of the delimiters is not found.
class Car
{
private String model,registration,colour;
private int year,mileage;
public Car(String mod,String r,String c,int y, int mil)
{
model=mod;
registration=r;
colour=c;
year=y;
mileage=mil;
}
}
Another easy five marks. You should have no problem giving a class
where all that is required are some fields and a constructor which
gives values to these fields.
public boolean older(Car c)
{
return year<c.year;
}
public boolean older(int y)
{
return year<y;
}
These methods would be called attached to a Car object,
in the first case the other Car object involved is given
as an argument, in the second case the check is against a year which is
given as an argument.
c is of type
CarChooser, then when it is used in
if(c.choose(nextCar)), where you are told that
nextCar is of type Car, you can work out
that the method choose takes a Car object
and returns a boolean. Only a call to a method which returns a
boolean can fit in as the ... in if(...).
So all we know of type carChooser is that it has a method
called choose which takes a Car object and
returns a boolean. That is enough to answer the question:
interface CarChooser
{
public boolean choose(Car c);
}
choose in it. A
ChooseByAge object is something which stores a year
internally when it is created, and when choose is called
on it with a Car object as the argument, returns
true if the car is older than that year, false
otherwise. So it makes use of the second of the older methods
defined in part b:
class ChooseByAge implements CarChooser
{
int myYear;
public ChooseByAge(int y)
{
myYear=y;
}
public boolean choose(Car c)
{
return !c.older(myYear+1);
}
}
Note that when older is called here with myYear+1
as its argument, the second of the two older methods will
be used because myYear+1 must be an Car object. Two methods like this, with the same name but
distinguished by different arguments types, are referred to as
overloaded.
class ChooseByMileage implements CarChooser
{
int myYear;
public ChooseByMileage(int m)
{
myMileage=m;
}
public boolean choose(Car c)
{
return c.lowerMileage(myMileage);
}
}
where the following extra method has to be added to class Car:
public lowerMileage(int m)
{
return mileage<m;
}
This is very similar to the answer to part ii, except that the
test that returns true or false is made
on the mileage of the car rather than the year of manufacture.
It is not possible to refer directly to the mileage field
of a Car object in class ChooseByMileage
because this field was declared as private in class
Car so cannot be referred to outside that class. That is
why the extra method lowerMileage is needed which has
to be added to class Car because there it can refer to
the mileage field of Car objects.