CSM41 Programming in Java 2011/12
Messages
 The files previously containing the incomplete code for Coursework II
(to be completed) now contain the solutions; see below.
 Coursework dates:
 First coursework: Handed out 25/10/2011, deadline 14/11/2011.
 Second coursework: Handed out 23/11/2011, deadline 14/12/2011.
General information
 First week (3/10/2011  7/10/2011):
 One lecture Friday 11:00  12:00 in the Robert Recorde room.
 One lab session Friday 12:00  13:00 in the Linux lab (room 217).
 This is a short session.
 The task is just to get used to the environment (knowing your
password, etc.).
 Tasks:
 Check that your login works.
 Access the course home page, and store the link.
 Browse the course home page, and get a bit familiar with it.
 From 10/10/2010 to 9/12/2010:
 Tuesday, 16:00  18:00, "support lab" session in the Linux lab
(room 217).
 Friday, 11:00  12:00, lecture in the Robert Recorde room.
 Friday 12:00  13:00, "exercise lab" session (Linux lab).
 The role of the support lab sessions:
 In the support lab sessions a mixture of teaching and programming
practice takes place.
 We might not make use of all support lab sessions.
 The role of the exercise lab sessions:
 Active participation in all exercise lab session is awarded 10% of
the overall module marks.
 For each exercise lab sessions tasks are distributed.
 During the exercise lab session, work on these tasks is expected.
 "Active participation" means that during the whole lab session
reasonable work related to the module is performed, typically related
to the current tasks, but possibly also related to previous tasks,
or to other questions or problems (of course, related to the module).
 There are no tests (or exams) in the labs. Every student present for
the full time and doing reasonable work gets acknowledged his/her
active participation.
 Assessment:
 10% is allocated to active participation in the exercise lab
sessions.
 Two courseworks are handed out, each worth 20%.
 The remaining 50% is the January exam.
 The exam is based on what we did in the lectures, the lab sessions,
and the coursework.

JonathanLee Jones
is the postgrad demonstrator.
The textbook
 This module is based on the book
 "Introduction to Programming in Java"
 from Robert Sedgewick and Kevin Wayne,
 AddisonWesley 2007 (ISBN13 9780321498052).
 It is strongly recommended that you buy this book
(for example at the Campus book shop).
 The book's home page is
here .
 Additional to the book, at this web page a lot of useful information
is available.
 Here is Chapter 1 as pdffile.
 In this module we cover the essentials from the first three chapter.
Slides and material for the lectures
The additional programs you find here .
 Week 2:
 Tuesday (11/10/2011):
 We write 3 programs together.
 Empty program:
class Empty {
public static void main(String[] args) {}
}
 HelloWorld:
class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello, World!");
}
}
 HelloWorld with three further names:
class UseArgument {
public static void main(String[] args) {
System.out.print("Hello, ");
System.out.print(args[0]);
System.out.print(", ");
System.out.print(args[1]);
System.out.print(", ");
System.out.print(args[2]);
System.out.println("!");
}
}
 Section 1.1 First programs .
 Here some remarks.
 Friday (14/10/2011): Section 1.2
Basic types .
 Week 3:
 Tuesday (18/10/2011):
 We look at the program "IntOps" in detail (
here is
the code).
 There are many problems with this program, and we try to write a
"perfect" version of it.
 We learn:

final
for declaring constants: Don't use
int a = Integer.parseInt(args[0]);
but
final int a = Integer.parseInt(args[0]);
for a variable whose value shouldn't be changed anymore (i.e., we
have a constant).
 The
length
variable to be used with
args
for finding out how many commandline arguments
were entered:
args.length
is an integer, namely the number of commandline arguments.

if
for conditional execution: Via
if (args.length <= 1)
System.err.println("ERROR[IntOpsI]: Two arguments are needed (two numbers).");
else
...
we output an errormessage in case we do not have two commandline
arguments.
 Here
is the improved version.
 There are further serious problems with input handling:
overflow and noninteger input. They can be handled using the
following constructions:

Integer.MIN_VALUE
and
Integer.MAX_VALUE
for finding out the range of int's.

try ... catch
for error handling via catching
exceptions.
 Finally we have problems with the structure of the code: too
many nested ifthenelse make the code messy, and it would be good
if we had also conditional variable initialisation:
 The
System.exit
function allows early return with
an exitcode.
 Conditional expressions allow to have several cases in the
initialisation of variables.
 Here
is the fully improved version.
 Friday (21/10/2011): Section 1.3
Program flow
(
if
statement and while
loop).
 Here some remarks and corrections.
 Week 4:
 Tuesday (25/10/2011):
 Completed Section 1.3
Program flow
(
for
loop and Gambler
program).
 Loops are very important, so please make sure you understand
this section.
 And understand the
Gambler
program in detail!
 Friday (28/10/2011): Section 1.4
Arrays (inclusive printing a
random card).
 Week 5:
 Tuesday (1/11/2011):
 Completing Section 1.4
Arrays
(
Deck
for card shuffling, CouponCollector
and SelfAvoidingWalk
).
 Friday (4/11/2011):
 Section 1.5
Input and output .
 See
here
for the inputoutput library we will use from now on.
 You can either copy the .javafiles from this library to the
directory with your programfiles, or you can precompile the library
(by "javac *"), and then just copy the .classfiles.
 Additional material you find
here.
 Week 6:
 Tuesday (8/11/2011):
 Completing Section 1.5
Input and output .
 Please enter all programs (still) by hand (no copyandpaste).
 This session completes the part on the basics of programming
(variables, expressions, basic types, loops, conditions, arrays).
 In the remainder of the module we will accelerate the speed.
 First
ShowArgs.java is
a little program helping you to understand the array of strings
args
, and how it gets its value; understand the
following:
> java ShowArgs jj k ll " b n " \"
[Ljava.lang.String;@3ce53108
5
0 : "jj"
1 : "k"
2 : "ll"
3 : " b n "
4 : """

RandomSeq.java
is a simple example programs which outputs N (pseudo)random numbers
to standard output.

Average.java
shows how to read an arbitrary stream of numbers from standard
input and computing their arithmetic mean.
 This program is improved over the book version by
 using more expressive code,
 checking for empty inputs,
 handling of input errors,
 and also allowing "arbitrarily" long input sequences (for all
practical purposes).

PlotFilter.java reads
(all from standard input)
 first four floatingpoint numbers for min x/yvalues and max
x/yvalues,
 and then an arbitrary sequence of points, specified by their
x,y coordinates (as floatingpoint numbers),
drawing each point when read.

SinFunction.java plots
the function sin(4x)+sin(20x) for 0 <= x <= pi.
 Have a look at the error handling, which uses errorcode
constants specified at classlevel.
 Note also that the constants "4" and "20" are not hardcoded.
 The commandline argument N is the number of points except the
first point, used to plot the function by connecting them.
 If N is not large enough, then the output can be very misleading.
 Friday (11/11/2011):
 Section 2.1
Functions .
 Week 7:
 Tuesday (15/11/2011):
 Practising functions (see Section 2.1
Functions ).
 Six programs have to be completed, filling the positions marked
with "XXX":
 Write a function
max(a,b)
, computing the maximum
of two integers:
 Write a function
max(a,b,c)
, computing the maximum
of three integers:
 Write a function
max(a,b,c,d)
, computing the maximum
of four integers:
 Write a function
max(a)
, computing the maximum
of an array of integers:
 Write a function
create(n)
, creating an integer
array of length n, filled with 0, 1, ..., n1:
 Write a function
print_message(name)
, outputting
"Hello, name!":
 Friday (18/11/2011):
 Section 2.2
Libraries and Clients .
 Week 8:
 Tuesday (22/11/2011):
 Using libraries
Libraries and Clients .
 Two programs have to be completed, filling the positions marked
with "XXX":
 Write a program
RandomPoints
which draws N
random points according to a Gaussian distribution:
 Write a program
Bernoulli
which experimentally
computes the relative frequency of 0 <= i <= N heads for N fair
coin flips, and compares it with the approximation by the
Gaussian distribution:
 Friday (25/11/2011):
 Section 3.1
Data types .
 Week 9:
 Tuesday (29/11/2011):
 Using other classes ("constructors" and "methods")
Data types .
 Two programs have to be completed, filling the positions marked
with "XXX":
 Write a program
AlbersSquares
which shows two
colours using two squares:
 Write a program
Grayscale
to convert a
colourpicture to a gray scale:
 Friday (2/12/2011):
 Section 3.2
Creating data types .
 Week 10:
 Tuesday (7/12/2010):
 Completing Section 3.2
Creating data types .
 Understanding "passbyvalue" and "passbyreference":
 What is the output of
PassByValue
?
 And which of the variables (arguments of function
update
and others) can be made final?
The solution is provided
here
.
 Aliasing:
 What is the output of
PotentialProblem
?
 What is the output of
PotentialProblem2
?
 What is the output of
PotentialProblem3
?
Understand that aliasing can not occur in the first two examples,
whatever we do, since the data types used for variable x are
immutable. And understand why using a "proper class", i.e.,
an array here, provided the additional level of indirection in the
third example so that aliasing finally occurs.
 The architecture of the second coursework:
 Read the code!
 Friday (10/12/2010):
 Section 3.3
Designing data types .
 Week 11:
 Tuesday (13/12/2011):
Revision and exampreparation lecture
.
 In January we have an additional exam preparation session.
Exercise lab sessions
Remark: If some answer is already given, then understand why
this is the correct answer.
 Week 2 (14/10/2011):
 The program "UseArgument.java" from the book is needed again 
rewrite it from scratch, not using notes!
 Recall that it is called with, e.g.,
> java UseArgument XYZ
and it outputs
Hi, XYZ. How are you?
 It's really important that you get the syntax into your fingers.
 If you get stuck, then have a tiny little glimpse into
the book, just to help you to continue.
 Do the Exercises from Section 1.1 (see
here at the
bottom, Exercises 1  5).
 Enter the program
public class LeftAssociative {
public static void main(String[] args) {
final int a = Integer.parseInt(args[0]);
final int b = Integer.parseInt(args[1]);
System.out.println(a + " + " + b + " = " + a + b); // not what is meant
System.out.println(a + " + " + b + " = " + (a + b));
System.out.println(a + b + " + " + "13" + " = " + (a + b + 13)); // understand this
}
}
 Play around with it, and understand what it is doing.
 The key is to understand that we have variables of two types,
int
and String
, and that automatic conversions
are performed from int
to String
if needed.
 Week 3 (21/10/2011):
 Enter the three programs from the lecture (Flip, PowersOfTwo, Sqrt),
run them with all sorts of different arguments, understand the
outcome.
 Especially try to crash the programs (missing or
strange inputs, very large or very small numbers, ...).
 After you did this for some time, consider the exercises from
Section 1.2 (see
here
after the "Q + A" section, Exercises 1  23).
 Exercises 1.2.1  1.2.14 are about understanding expressions.
 Write little programs which compute the expressions, possibly
for all inputs (especially in the case of boolean expressions).
 If you wish to write a new program, consider 1.2.14  1.2.23.
 Week 4 (28/10/2011):
 Write a program which reads two integers and prints them out sorted
in ascending order.
 Write another program which reads three integers and prints them
out sorted in ascending order.
 Write better versions of "TenHellos.java" (printing "Hello World!"
ten times), using first a whileloop and then a forloop. Which
is better?
 Write the programs "ModularAddition" and "ModularMultiplication"
as mentioned below in the first coursework.
 Consider exercises 1.3.1  1.3.7 from the book (see
here);
perhaps first considering exercises 1, 3, 4 (perhaps writing a complete
program), 6 (again perhaps writing programs to testing your answer)
and 7.
See here
for solutions. Additional exercises:
 Write a program which reads an integer N and computes the sum
1 + 2 + ... + N.
 Write a program which reads an integer N and computes the product
1 * 2 * ... * N; choose a suitable data type so that some interesting
computations can be performed!
 Enter the program "Gambler" from the lecture, and play around with
it a bit.
 Improve the output of "Gambler":
 Print out the inputs, with additional explanations.
 Print out the frequency wins/T (where T is the number of
trials).
 Print out the probability stake/goal of winning.
 Print out the expected number of steps (stake)*(goalstake).
 Finally determine the average and the maximum number of steps
it took to finish a trial (that is, the number of steps until cash
either is 0 or goal), and print it out.
 Consider exercises 1.3.8  1.3.31 from the book (see
here).
See here
for solutions.
 Week 5 (4/11/2011):
 Write a program "Deck32" (recall "Deck"), which uses only a deck of
32 cards, where the ranks do not include 2 up to 6.
 Now combine "Deck" and "Deck32" into one program, where via a
commandline argument it is decided whether 32 or 52 cards are to be
used.
 Consider exercises 1.4.1  1.4.9 from the book (see
here).
 Consider exercise 1.4.35 from the book ("Birthday.java", see
here).
 Week 6 (11/11/2011):
 Consider exercises 1.5.1  1.5.3 from the book (see
here):
 Write a program that reads in integers (as many as the user
enters) from standard input and prints out the maximum and minimum
values. Before entering the program, make a sketch on paper.
 Modify this program by rejecting nonpositive entries, asking the
user to reenter the input (until he gets it correct). Before
entering the program, extend the previous sketch. Hint: a whileloop
is appropriate for testing the input values.
 Read N from the commandline and N floatingpoint number from
standard input, and compute their mean value. Create an error message
if not enough numbers were entered. Compute also the standard
deviation as the square root of the sum of the squares of the
differences from these numbers and the average, the whole then divided
by N1. Hint: For this computation you could store the numbers in
an array.
Always test your programs thoroughly!
 Consider exercise 1.5.7 from the book: Read in N from the
commandline plus N1 integers from 1 to N from standard input, assuming
that these numbers are different. Now determine the missing number (from
the interval 1 .. N).
 As an additional exercise, improve
PlotFilter.java
by not asking for the minimum x/y values, but computing them from
the input (so the first four special doubles from standard input are not
needed anymore). Test with
USA.txt, where you
removed the first four numbers.
 Week 7 (18/11/2011):
 Consider exercises 2.1.1  2.1.4 from the book (see
here).
 As additional exercises you can consider 2.1.13, 2.1.14 and 2.1.17.
 Week 8 (25/11/2011):
 If you didn't finish the exercises from last week, then please
finish them now (we are still on functions).
 Consider exercises 2.1.5, 2.1.12, 2.1.18, 2.1.19 and 2.1.20
from the book (see
here).
 For exercise 2.1.18, if for example the input is the array
(1,3,7), then the output should be (0,3/7,1). And if the
input is (10,4,1), then the output should be (0,6/9,1).
 Additional exercises on multidimensional arrays:
 Hardcode a 3 x 3 array of integers with the values
1 2 3
4 5 6
7 8 9
and print it out.
 Write a function
print_array(A)
in a class
PrintArray
which prints out an arbitrary twodimensional
array of integers, rowwise. Handle the general case, where every row
can have a different length. And if nullpointers occur for a row
, then print "[null]", while if the whole array is null, then print
"[[null]]" (no exceptions should be thrown).
 Add a main function to class
PrintArray
which tests
function print_array(A)
.
 Read natural numbers M and N from the command
line, specifying an M x N array of integers. Then read from standard
input (using
StdIn
) rowwise these M*N many integers,
and store them in an array. Finally print them out, using
PrintArray.print_array
.
See here for
solutions.
 Week 9 (2/12/2011):
 See the two exercises above for the Tuesdaylecture
(writing programs
AlbersSquares
and Grayscale
).
 Further exercises using the data types "Color" and "Picture" from
the lecture (see above):
 Exercise 3.1.2 from the book: Write a program that takes from the
commandline three integers from 0 to 255 (representing red, green
and blue), and then creates and shows a 256by256 picture of that
colour.
 Exercise 3.1.3 from the book: Modify program "AlbersSquares" to
take nine commandline arguments, representing now three colours, and
then draw the 3*2=6 squares showing all the Albers squares with the
large square in each colour and the small square in each different
colour.
 Exercise 3.1.6 from the book: Write a program that takes the name
of a picture file as a commandline input, and creates three images,
one that contains only the red components, one for green, and one for
blue.
 Exercise 3.1.4 from the book:
 Write a program that takes the name of a grayscale picturefile
as a commandline argument, and plots a histogram of the frequency
of occurrences of each of the 256 grayscale intensities.
 Use the library "StdStats" from Section 2.2 (provided
here ).
 Another (simple) arrayexercises:
 Read N from the commandline.
 Create an NxN array A of integers, where the first row contains
0,1,..., the second row contains 1,2,..., and so on.
 Then add all the numbers on the principal diagonal (that is,
A[0,0] + A[1,1] + ...), and print out the result.
 You can easily check whether your program works: the result should
be N*(N1).
 Use one function for creating the array.
 And use another function for computing the diagonal sum.
The solution is
here
.
 Finally we practise using static data members ("static instance
variables"). Write a class
StringExample
:
 Containing (static) constants
size_a
of
value 4 and array a
containing the four strings "AB",
"XYZ", "EFG", "1234".
 We also have
size_b
of value 3, and array
b
containing the three strings "M1", "T3", "y6".
 Furthermore we have a static function
check_a
which
takes one string argument x, and returns integers from 0 to 3 if the
string x occurs in array a
with that index, while
otherwise 1 is returned.
 And in the same vein we have
check_b
.
 Both functions must use a loop for checking the membership in the
respective array.
 The main programs reads pairs of strings from standard input (as
long as standard input has not been closed), and prints out the results
of
check_a, check_b
.
 For example "EFG T3" results in "2 1", and "X y6" results in
"1 2".
Here is
the solution .
 Week 10 (10/12/2010):
 Creating and using a trivial class:
 Write a class
Trivial
, which stores two integers (via
the constructor), and as member functions ("methods") allows to
compute their sum and to translate the object into a string.
 Write then a program which reads four integers from the
commandline, creates two objects of type
Trivial
accordingly, and outputs their sums and the objects themselves.
Here is
the Trivialsolution , and here is the
Client .
 Study "Charge.java" and "Potential.java", understand how it works,
and play a bit around (using for example "charges.txt" as input).
 Study
Turtle.java and the application
Spiral.java ;
play a bit around with it, and write your own clients of class Turtle,
creating some simple turtlegraphics.
 Additional exercises:
 More on arrays (and static functions):
 Counting random events:
 Write a program (class) "RandomNumbers" which takes two
commandline arguments M and N.
 The program then creates N many random integers in the interval
[1, M], counts how often each of these integers occurs, and then
prints out the relative frequency for each of these M numbers (that is,
the quotient "occurrences / N").
 Your program should work for large N, and thus should not store
the N random numbers computed.
 For the creation of the random integer write a function
random(M)
, which takes M as parameter, and returns a
random integer from 1 to M.
 Hint: you need to use an integerarray of size M for performing
the counting.
Here is
the solution .
 More on modules (or "libraries"):
 Implement the library class StdStats with (just) the static
functions "min", "max" and "mean".
 Write a program "Stats" which is called with floating point
numbers as commandline parameters, and which computes their
minimum, maximum and average, using your library StdStats.
 For example, "Stats 4 5.2" would yield min=4, max=5.2,
mean=4.6.
 Parsing strings (using methods from the
String
class)
 Read a string from the commandline and determine how many
spaceseparated parts it has.
 Modify the solution of the previous part, where now the string is
split at the symbol "@".
 Again, play around with it (what happens when spaces are used?).
 Here is a
solution
which again shows the parts with their indices.
 Parse a string, where you extract all digits from it, adding them
up, returning their sum and the original string without these digits:
 Recursion (we didn't do that section from Chapter 2):
 Enter the program "Htree" from the book.
 Write a modified program "Htree2", which asks for confirmation
before continuing drawing parts of the tree.
 Also print out appropriate messages, so that you can follow in
detail the recursion.
 Run the program for inputs up to 4, and make sure you understand
what's going on!
Here is
a solution .
Coursework
First coursework
 Deadline for submission is 14/11/2011, 15:00.
 This coursework has to be electronically submitted:
 Four Javafiles, named "Sort4.java", "ModularPower.java",
"DiscreteLogarithm.java" and "ElementOrder.java", together with
a file "Comments.txt" have to be put into a directory named with
just your studentnumber (e.g., "123456"), this put into one archive,
for example "123456.zip", and this archive must be send to me via
email.
 To emphasise: You send to me, as attachment, one
file, which is a package in some standard format, zip or gzip for
example, named "123456.zip" or "123456.tar.gzip" for example, and which
contains one directory (named by your student number, e.g., "123456"),
and where this directory contains again (precisely) five files (four
Javafiles, one textfile).
 I'll send you an acknowledgement, once I got your packagefile.
 To make this safer, it would be good if in your email you could
state the md5sumresult for your packagefile (e.g., "123456.zip"). For
a Windowsenvironment see e.g.
here for how
to do this (in a Linuxsystem, use "md5sum 123456.zip" on a
commandline).
 This process has been found considerably more reliable than
submission via Blackboard.
 The file "Comments.text" must start with your name and student number,
and can then contain any comments or explanations you might want to make.
 Good coding quality is paramount:
 You must have tested your code (compiled it and run it).
 Syntax errors will result in deductions.
 Of course, false outputs will also result in deductions.
 Use only the Java constructions presented in the lectures.
 Anything else will result in a deduction of 50 percent! (The same
will hold for the second coursework.)
 This is to make sure that you really concentrate on the essentials,
and don't copyandpaste code (which usually contains a lot of noise).
 Compared to the book, we introduced a few extensions in the lectures,
most important the
final
qualifier, which you are expected
to use.
 Also some input checking (as discussed in the lectures) is important.
 Take care about precise class and filenames.
 Choose good variablenames.
 Provide a wellorganised indentation.
 Finally, follow precisely the specification: Not
just regarding the values of the output, but also regarding the precise
formatting!
 For each of the four programs to be written you can get 30 marks,
which makes 120 marks altogether, which are capped at 100.
 The four programs

Sort4

ModularPower

DiscreteLogarithm

ElementOrder
are likely best approached in this order (of increasing difficulty).
 The first programs concerns conditionals (only), the second and the
third additionally also loops, and the fourth additionally also arrays.
 Specification of
Sort4
:
 This programs takes four integers as parameters, and returns them
in sorted order.
 E.g. (omitting here and in the sequel the
java
command):
> Sort4 1 2 3 4
1 2 3 4
>Sort4 8 7 7 2
2 7 7 8
 Notice that in the nonerror case there is no text output, just
the 4 numbers, separated by a space, closing with endofline.
 An additional requirement concerns the number of comparisons used
by your program: for each inputsequence, only at most 5 comparisons
are to be used!
 Of course, the solution must use only elementary means, that is,
only using conditionals and assignments. The only library functions
used are for input and output.
 Modular arithmetic: the basic idea.
 The remaining three exercises concern "modular arithmetic".
 A "modulus" n is given, a natural number greater zero.
 Recall that for an integer x the Java operation "remainder", i.e.,
x % n
, produces a natural number from 0 to n1 (inclusive).
 Now "modular arithmetic" (with the integers) basically means, that
before and after performing additions and multiplications, one replaces
operands and result by the remainder with n.
x + y mod n := ((x % n) + (y % n)) % n
x * y mod n := ((x % n) * (y % n)) % n
 In this way one keeps all numbers small.
 Arithmetic modulo 2, the first nontrivial case, is the the
arithmetic of even and odd.
 Some concrete examples:
 6 + 10 mod 5 = 1 + 0 mod 5 = 1.
 77 + 20 mod 15 = 2 + 5 mod 15 = 7.
 77 + 14 mod 15 = 2 + 14 mod 15 = 1.
 3 * 7 mod 5 = 3 * 2 mod 5 = 1.
 3 * 7 mod 21 = 0.
 You might want to write two little programs, "ModularAddition" and
"ModularMultiplication", to play around with it:
> ModularAddition 6 10 5
1
> ModularMultiplication 3 7 21
0
 A final remark: Due to the deficient handling of negative numbers
in Java w.r.t. the remainderoperation, we only consider nonnegative
integers here.
 Specification of
ModularPower
:
 This program takes three integer parameters a, e, n, and computes
a^e mod n (the power of a to e, modulo n).
 The exponent e is not directly part of the modular arithmetic (it is
not reduced by the remainder operation), and we only consider
nonnegative e.
 Recall that a^0=1 for all a (and thus also 0^0 = 1).
 Since for n=1 (computing modulo 1) we have "0=1", in that special
case it means 0^0 = 0.
 Some examples:
> ModularPower 0 5 7
0
> ModularPower 0 0 1
0
> ModularPower 0 0 2
1
> ModularPower 2 3 5
3
> ModularPower 2 1234567890 777777777
383814208
> ModularPower 1000000000 56789 1000000001
1000000000
 Note that in the nonerror case just a number is output.
 Specification of
DiscreteLogarithm
:
 This program takes three integer parameters a, b, n, and computes
the smallest exponent 0 <= e < n with b^e = a mod n.
 That is, the "discrete logarithm" of a to base b modulo n.
 It is the inverse of
ModularPower
.
 In case there is no e, the result shall be "1".
 Some examples:
> DiscreteLogarithm 0 0 1
0
> DiscreteLogarithm 0 0 2
1
> DiscreteLogarithm 1 2 2
0
> DiscreteLogarithm 0 2 2
1
> DiscreteLogarithm 5 2 7
1
> DiscreteLogarithm 5 3 7
5
> DiscreteLogarithm 2 3 5
3
> DiscreteLogarithm 3 2 777777777
1
> DiscreteLogarithm 383814208 2 777777777
3690
> DiscreteLogarithm 3 10 1111111181
898664729
 Note that, again, in the nonerror case no text is output.
 Specification of
ElementOrder
:
 This program takes two integer parameters a, n, and computes how
many different elements can be obtained by repeated multiplication of
a with itself modulo n, i.e., considering a^1 mod n, a^2 mod n, ...,
and counting how many different numbers can be obtained.
 Note that the result is always between 1 and n (inclusive).
 Some examples:
> ElementOrder 0 1
1
> ElementOrder 1 5
1
> ElementOrder 2 5
4
> ElementOrder 2 8
3
> ElementOrder 6 10000019
10000018
> ElementOrder 5 100000007
100000006
> ElementOrder 1000000 1000001
2
 General remark: All programs are rather small: A few lines for reading
the input, a few lines for error handling, and a few lines for the core
computation.
Here are the solutions:
Second coursework: TicTacToe (generalised)
Formal requirements:
 Deadline for submission is 14/12/2011, 15:00.
 This coursework has to be submitted electronically:
 All the javafiles which constitute "GeneralisedTicTacToe", together
with a file "Comments.txt" have to be put into a directory named by
just your studentnumber (e.g., "123456"), this put into one archive,
for example "123456.zip", and this archive must be send to me via
email.
 To emphasise: You send to me, as attachment, one
file, which is a package in some standard format, zip or gzip for
example, named "123456.zip" or "123456.tar.gzip" for example, and which
contains one directory (named by your student number, e.g.,
"123456"), and where this directory contains the javafiles and the
textfile.
 I'll send you an acknowledgement, once I got your packagefile.
 To make this safer, it would be good if in your email you could
state the md5sumresult for your packagefile (e.g., "123456.zip"). For
a Windowsenvironment see e.g.
here for how
to do this (in a Linuxsystem, use "md5sum 123456.zip" on a
commandline).
 This process has been found considerably more reliable than
submission via Blackboard.
 The file "Comments.text" must start with your name and student number,
and can then contain any comments or explanations you might want to make.
 The structure and much of the code is already given, only at the places
marked with "XXX" are you expected to add code.
 You might also add further (private) helper functions.
 You might add new classes if you wish to implement the
machineplaying functionality.
 Good coding quality is paramount:
 You must have thoroughly tested your code  compiled it and run it
often!
 Use only the Java constructions presented in the lectures.
 Anything else will result in a deduction of 50 percent!
 This is to make sure that you really concentrate on the essentials,
and don't copyandpaste code (which usually contains a lot of noise).
 Compared to the book, we introduced a few extensions in the lectures,
most important the
final
qualifier, which you are expected
to use.
 Input checking (as discussed in the lectures) is important.
 Take care about precise class and filenames (if you have to
introduce new classes; this is only needed if you add capabilities
for computerplay).
 Choose good variablenames.
 Provide a wellorganised indentation.
 Finally, follow precisely the specifications!
General overview:
 We implement the game "Tictactoe" (or "Noughts and Crosses");
see
Wikipedia
for general information.
 Actually, we will consider the generalisation
"KINAROW ON AN MBYN BOARD"; see
here
for background information.
 The main task is just to support two human players playing against
each other.
 Optional extensions consider some basic techniques for machineplaying.
 The decomposition of this task into small tasks (via functions) is
already given.
 The code below contains all the major functions.
 Open places are marked by "XXX" (to be filled out).
 The given structure has to be followed:
 on the one hand, otherwise the task would be very hard,
 and on the other hand, in almost all professional situations
also most of the code (and especially the general structure) has
already been established.
 The main program:
 The commandline call is
GeneralisedTicTacToe K M N hh/hc/ch/cc
.
 For example for two humans playing ordinary tictactoe:
> java ea GeneralisedTicTacToe 3 3 3 hh
 Note the option "ea" here, which enables assertions:
 The given code contains many assertions, and they are enabled with
this option.
 The assertions spell out (most of) the prerequisites for function
calls and executions of instructions which might fail.
 In debugmode these assertions should be enabled.
 While finally, when the program really is used, the assertions are
not to be activated (since they can require long runtimes).
 In hhmode (humanhuman) your program then reads the moves of the
two players, handling appropriately (all!) input errors, and determines
the outcome.
 Also the intermediate and final positions are to be displayed
(simple text modus).
 Here is a simple run, using standard tictactoe:
> java GeneralisedTicTacToe 3 3 3 hh
Starting GeneralisedTicTacToe.
Number of rows: 8
Occurrences:
3 2 3
2 4 2
3 2 3
The game begins.
123
1: ...
2: ...
3: ...
Player I has to move.
2 2
Move of player I: 2 2
123
1: ...
2: .X.
3: ...
Maximal occupation number of new cell: 1
Player II has to move.
2 1
Move of player II: 2 1
123
1: ...
2: 0X.
3: ...
Maximal occupation number of new cell: 1
Player I has to move.
1 3
Move of player I: 1 3
123
1: ..X
2: 0X.
3: ...
Maximal occupation number of new cell: 2
Player II has to move.
3 1
Move of player II: 3 1
123
1: ..X
2: 0X.
3: 0..
Maximal occupation number of new cell: 2
Player I has to move.
1 1
Move of player I: 1 1
123
1: X.X
2: 0X.
3: 0..
Maximal occupation number of new cell: 2
Player II has to move.
3 3
Move of player II: 3 3
123
1: X.X
2: 0X.
3: 0.0
Maximal occupation number of new cell: 2
Player I has to move.
1 2
Move of player I: 1 2
123
1: XXX
2: 0X.
3: 0.0
Maximal occupation number of new cell: 3
The first player wins.
The final position is:
123
1: XXX
2: 0X.
3: 0.0
The complete list of moves is:
1.I : 2 2
1.II: 2 1
2.I : 1 3
2.II: 3 1
3.I : 1 1
3.II: 3 3
4.I : 1 2
 Your output should look rather similar to this one.
 Regarding input, no other input than the coordinates from the
moves must be used.
 In directory
Testgames
some testing examples for
input are given, and your program must be able to run them
via for example
cat 3_1_6_1  java GeneralisedTicTacToe 3 1 6 hh
 Note that the first three numbers in the filename are K,M,N, while
the fourth is the result ("0" is draw, "1" first player wins, "2"
second player wins).
The tasks:
 All files are to be found
here
.
 You need to study carefully the javafiles, in order to gain an
understanding of the design of this system.
 Marks are distributed on the different tasks (completing the
classes) as follows (as usual, marks are capped at 100):

GeneralisedTicTacToe.java
: 20

Parameters.java
: 10

Field.java
: 20

Input.java
: 10

Rows.java
: 30

Occurrences.java
: 20
 The above implements only mode "hh" (human against human). For
providing also computerplaying the following marks can be gained:
 Implementing all four modes, where the computer just chooses
any correct move: 30 marks.
 If the computer sees always if the player can win immediately:
additionally 10 marks.
 If the computer prevents if possible a win of the opponent in
one move: 10 marks.
 Your program must never crash! All input errors must be handled,
and messages issued (before possibly exiting the program).
 Cases which are not handled, must be "handled" by outputting the
notimplementedmessage (already provided).
 Also winnings and losses must be output using the provided
messages.
 Some remarks on the tasks:

GeneralisedTicTacToe.java
:
 My solution has 22 lines. Likely you need more lines, but beyond
50 lines I guess there is a chance that you are doing something wrong.
 The various cases (first versus second player, interrupt, some
player wins, or game finishes) need to be organised.
 You need to find out which of the variables are involved here
and need updating.
 Which of the provided functions are to be used?
 And which of the provided messages are needed?

Parameters.java
:
 Here the task is to understand input and output. Otherwise it is
straightforward.
 First XXX: My solution has 13 lines.
 Second XXX: My solution has 8 lines.

Field.java
:
 Read the code! Only in this way do you get a full understanding
of the whole program.
 First XXX: My solution has 13 lines; likely you need more, but it
is all straightforward.
 Second XXX: My solution has 12 lines; likely you need more, but
again it is all straightforward.

Input.java
:
 My solution has 13 lines; I don't think you need more than 30
lines.
 Understand that it is an endless loop, only terminated by the
end of standard input or by correct input.
 Of course, you need to use
StdIn
.
 And use the provided message.

Rows.java
:
 Compute various arrays first by hand, to understand the task.
 Regarding the two examples given in the fileheader: The order of
the rows, and also the order of cells in the rows, is not important.
All what counts is that you get all rows in some order, and that the
rows have all their cells (in some order).
 My solution has 50 lines.
 If you have trouble here, first consider the special case
k=m=n=3 and r=8.
 I think it is easiest to consider the four directions (horizontal,
vertical, topleft to bottomright, bottomleft to topright)
separately.
 It is all rather simple, it only needs some organised thinking,
to create a scheme for the creation of the various rowtypes.
 Use asserts!

Occurrences.java
:
 If you use a different order of the rows, then your occurrences
(of cells in rows) will differ from the given example.
 First XXX: depending on how you do it, the one line might become
two (or even three).
 Second XXX: My solution has 13 lines; you might use more, but it's
all straightforward.
 Again, read all the code!
Links
 A
Git repository is available, where you can download the source
code repository.
 There you also find C++ versions.
Reading