CS-M41 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:
1. First coursework: Handed out 25/10/2011, deadline 14/11/2011.
2. Second coursework: Handed out 23/11/2011, deadline 14/12/2011.

General information

First week (3/10/2011 - 7/10/2011):
1. One lecture Friday 11:00 - 12:00 in the Robert Recorde room.
2. One lab session Friday 12:00 - 13:00 in the Linux lab (room 217).
  1. This is a short session.
  2. The task is just to get used to the environment (knowing your password, etc.).
  3. 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:
1. Tuesday, 16:00 - 18:00, "support lab" session in the Linux lab (room 217).
2. Friday, 11:00 - 12:00, lecture in the Robert Recorde room.
3. Friday 12:00 - 13:00, "exercise lab" session (Linux lab).
The role of the support lab sessions:
1. In the support lab sessions a mixture of teaching and programming practice takes place.
2. We might not make use of all support lab sessions.
The role of the exercise lab sessions:
1. Active participation in all exercise lab session is awarded 10% of the overall module marks.
2. For each exercise lab sessions tasks are distributed.
3. During the exercise lab session, work on these tasks is expected.
4. "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).
5. 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:
1. 10% is allocated to active participation in the exercise lab sessions.
2. Two courseworks are handed out, each worth 20%.
3. The remaining 50% is the January exam.
4. The exam is based on what we did in the lectures, the lab sessions, and the coursework.
Jonathan-Lee 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,
- Addison-Wesley 2007 (ISBN-13 978-0-321-49805-2).
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 pdf-file.
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) {}
}

Hello-World:

class HelloWorld {
  public static void main(String[] args) {
    System.out.println("Hello, World!");
  }
}

Hello-World 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:
1. Tuesday (18/10/2011):
  1. We look at the program "IntOps" in detail ( here is the code).
  2. There are many problems with this program, and we try to write a "perfect" version of it.
  3. We learn:
    1. 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).
    2. The length-variable to be used with args for finding out how many command-line arguments were entered:
```
args.length
          
```
      is an integer, namely the number of command-line arguments.
    3. if for conditional execution: Via
```
if (args.length <= 1)
  System.err.println("ERROR[IntOpsI]: Two arguments are needed (two numbers).");
else
  ...
          
```
      we output an error-message in case we do not have two command-line arguments.
    4. Here is the improved version.
    5. There are further serious problems with input handling: overflow and non-integer input. They can be handled using the following constructions:
      1. Integer.MIN_VALUE and Integer.MAX_VALUE for finding out the range of int's.
      2. try ... catch for error handling via catching exceptions.
    6. Finally we have problems with the structure of the code: too many nested if-then-else make the code messy, and it would be good if we had also conditional variable initialisation:
      1. The System.exit function allows early return with an exit-code.
      2. Conditional expressions allow to have several cases in the initialisation of variables.
  4. Here is the fully improved version.
2. Friday (21/10/2011): Section 1.3 Program flow (if-statement and while-loop).
3. Here some remarks and corrections.
Week 4:
1. Tuesday (25/10/2011):
  1. Completed Section 1.3 Program flow (for-loop and Gambler-program).
  2. Loops are very important, so please make sure you understand this section.
  3. And understand the Gambler-program in detail!
2. Friday (28/10/2011): Section 1.4 Arrays (inclusive printing a random card).
Week 5:
1. Tuesday (1/11/2011):
  1. Completing Section 1.4 Arrays (Deck for card shuffling, CouponCollector and SelfAvoidingWalk).
2. Friday (4/11/2011):
  1. Section 1.5 Input and output .
  2. See here for the input-output library we will use from now on.
  3. You can either copy the .java-files from this library to the directory with your program-files, or you can precompile the library (by "javac *"), and then just copy the .class-files.
  4. Additional material you find here.
Week 6:
1. Tuesday (8/11/2011):
  1. Completing Section 1.5 Input and output .
  2. Please enter all programs (still) by hand (no copy-and-paste).
  3. This session completes the part on the basics of programming (variables, expressions, basic types, loops, conditions, arrays).
  4. In the remainder of the module we will accelerate the speed.
  5. 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 : """
       
```
  6. RandomSeq.java is a simple example programs which outputs N (pseudo)random numbers to standard output.
  7. Average.java shows how to read an arbitrary stream of numbers from standard input and computing their arithmetic mean.
  8. 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).
  9. PlotFilter.java reads (all from standard input)
    1. first four floating-point numbers for min x/y-values and max x/y-values,
    2. and then an arbitrary sequence of points, specified by their x,y coordinates (as floating-point numbers),
    drawing each point when read.
  10. SinFunction.java plots the function sin(4x)+sin(20x) for 0 <= x <= pi.
    1. Have a look at the error handling, which uses error-code constants specified at class-level.
    2. Note also that the constants "4" and "20" are not hard-coded.
    3. The command-line argument N is the number of points except the first point, used to plot the function by connecting them.
    4. If N is not large enough, then the output can be very misleading.
2. Friday (11/11/2011):
  1. Section 2.1 Functions .
Week 7:
1. Tuesday (15/11/2011):
  - Practising functions (see Section 2.1 Functions ).
  - Six programs have to be completed, filling the positions marked with "XXX":
    1. Write a function max(a,b), computing the maximum of two integers:
      - Template
      - Solution
    2. Write a function max(a,b,c), computing the maximum of three integers:
      - Template
      - Use the function handling 2 arguments!
      - Solution
    3. Write a function max(a,b,c,d), computing the maximum of four integers:
      - Template
      - Use the functions handling 2 and 3 arguments!
      - Solution
    4. Write a function max(a), computing the maximum of an array of integers:
      - Template
      - What happens for zero numbers?
      - Solution
    5. Write a function create(n), creating an integer array of length n, filled with 0, 1, ..., n-1:
      - Template
      - What happens for n <= 0?
      - Solution
    6. Write a function print_message(name), outputting "Hello, name!":
      - Template
      - Solution
2. Friday (18/11/2011):
  1. Section 2.2 Libraries and Clients .
Week 8:
1. Tuesday (22/11/2011):
  1. Using libraries Libraries and Clients .
  2. Two programs have to be completed, filling the positions marked with "XXX":
    1. Write a program RandomPoints which draws N random points according to a Gaussian distribution:
      - Template
      - Solution
    2. 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:
      - Template
      - Solution
2. Friday (25/11/2011):
  1. Section 3.1 Data types .
Week 9:
1. Tuesday (29/11/2011):
  1. Using other classes ("constructors" and "methods") Data types .
  2. Two programs have to be completed, filling the positions marked with "XXX":
    1. Write a program AlbersSquares which shows two colours using two squares:
      - Template
      - Solution
    2. Write a program Grayscale to convert a colour-picture to a gray scale:
      - Template
      - Solution
2. Friday (2/12/2011):
  1. Section 3.2 Creating data types .
Week 10:
1. Tuesday (7/12/2010):
  1. Completing Section 3.2 Creating data types .
  2. Understanding "pass-by-value" and "pass-by-reference":
    1. What is the output of PassByValue ?
    2. And which of the variables (arguments of function update and others) can be made final? The solution is provided here .
    3. Aliasing:
      1. What is the output of PotentialProblem ?
      2. What is the output of PotentialProblem2 ?
      3. 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.
  3. The architecture of the second coursework:
    1. Read the code!
2. Friday (10/12/2010):
  1. Section 3.3 Designing data types .
Week 11:
1. Tuesday (13/12/2011): Revision and exam-preparation lecture .
2. 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):
1. The program "UseArgument.java" from the book is needed again --- rewrite it from scratch, not using notes!
  1. Recall that it is called with, e.g.,
```
> java UseArgument XYZ
        
```
    and it outputs
```
Hi, XYZ. How are you?
        
```
  2. It's really important that you get the syntax into your fingers.
  3. If you get stuck, then have a tiny little glimpse into the book, just to help you to continue.
2. Do the Exercises from Section 1.1 (see here at the bottom, Exercises 1 - 5).
3. 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
  }
}
      
```
4. Play around with it, and understand what it is doing.
5. 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):
1. Enter the three programs from the lecture (Flip, PowersOfTwo, Sqrt), run them with all sorts of different arguments, understand the outcome.
2. Especially try to crash the programs (missing or strange inputs, very large or very small numbers, ...).
3. 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):
1. Write a program which reads two integers and prints them out sorted in ascending order.
2. Write another program which reads three integers and prints them out sorted in ascending order.
3. Write better versions of "TenHellos.java" (printing "Hello World!" ten times), using first a while-loop and then a for-loop. Which is better?
4. Write the programs "ModularAddition" and "ModularMultiplication" as mentioned below in the first coursework.
5. 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:
1. Write a program which reads an integer N and computes the sum 1 + 2 + ... + N.
2. 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!
3. Enter the program "Gambler" from the lecture, and play around with it a bit.
4. 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)*(goal-stake).
  - 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.
5. Consider exercises 1.3.8 - 1.3.31 from the book (see here).
See here for solutions.
Week 5 (4/11/2011):
1. Write a program "Deck32" (recall "Deck"), which uses only a deck of 32 cards, where the ranks do not include 2 up to 6.
2. Now combine "Deck" and "Deck32" into one program, where via a command-line argument it is decided whether 32 or 52 cards are to be used.
3. Consider exercises 1.4.1 - 1.4.9 from the book (see here).
4. Consider exercise 1.4.35 from the book ("Birthday.java", see here).
Week 6 (11/11/2011):
1. Consider exercises 1.5.1 - 1.5.3 from the book (see here):
  1. 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.
  2. Modify this program by rejecting non-positive entries, asking the user to re-enter the input (until he gets it correct). Before entering the program, extend the previous sketch. Hint: a while-loop is appropriate for testing the input values.
  3. Read N from the command-line and N floating-point 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 N-1. Hint: For this computation you could store the numbers in an array.
  Always test your programs thoroughly!
2. Consider exercise 1.5.7 from the book: Read in N from the command-line plus N-1 integers from 1 to N from standard input, assuming that these numbers are different. Now determine the missing number (from the interval 1 .. N).
3. 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):
1. Consider exercises 2.1.1 - 2.1.4 from the book (see here).
2. As additional exercises you can consider 2.1.13, 2.1.14 and 2.1.17.
Week 8 (25/11/2011):
1. If you didn't finish the exercises from last week, then please finish them now (we are still on functions).
2. Consider exercises 2.1.5, 2.1.12, 2.1.18, 2.1.19 and 2.1.20 from the book (see here).
3. 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).
4. Additional exercises on multidimensional arrays:
  1. Hard-code a 3 x 3 array of integers with the values
```
1 2 3
4 5 6
7 8 9
        
```
    and print it out.
  2. Write a function print_array(A) in a class PrintArray which prints out an arbitrary two-dimensional array of integers, row-wise. Handle the general case, where every row can have a different length. And if null-pointers occur for a row , then print "[null]", while if the whole array is null, then print "[[null]]" (no exceptions should be thrown).
  3. Add a main function to class PrintArray which tests function print_array(A).
  4. 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) row-wise 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):
1. See the two exercises above for the Tuesday-lecture (writing programs AlbersSquares and Grayscale).
2. Further exercises using the data types "Color" and "Picture" from the lecture (see above):
  1. Exercise 3.1.2 from the book: Write a program that takes from the command-line three integers from 0 to 255 (representing red, green and blue), and then creates and shows a 256-by-256 picture of that colour.
  2. Exercise 3.1.3 from the book: Modify program "AlbersSquares" to take nine command-line 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.
  3. Exercise 3.1.6 from the book: Write a program that takes the name of a picture file as a command-line input, and creates three images, one that contains only the red components, one for green, and one for blue.
  4. Exercise 3.1.4 from the book:
    - Write a program that takes the name of a grayscale picture-file as a command-line 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 ).
3. Another (simple) array-exercises:
  1. Read N from the command-line.
  2. Create an NxN array A of integers, where the first row contains 0,1,..., the second row contains 1,2,..., and so on.
  3. Then add all the numbers on the principal diagonal (that is, A[0,0] + A[1,1] + ...), and print out the result.
  4. You can easily check whether your program works: the result should be N*(N-1).
  5. Use one function for creating the array.
  6. And use another function for computing the diagonal sum.
  The solution is here .
4. 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):
1. 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 command-line, creates two objects of type Trivial accordingly, and outputs their sums and the objects themselves.
  Here is the Trivial-solution , and here is the Client .
2. Study "Charge.java" and "Potential.java", understand how it works, and play a bit around (using for example "charges.txt" as input).
3. 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 turtle-graphics.
Additional exercises:
- More on arrays (and static functions):
  1. Counting random events:
    1. Write a program (class) "RandomNumbers" which takes two command-line arguments M and N.
    2. 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").
    3. Your program should work for large N, and thus should not store the N random numbers computed.
    4. 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.
    5. Hint: you need to use an integer-array of size M for performing the counting.
    Here is the solution .
- More on modules (or "libraries"):
  1. Implement the library class StdStats with (just) the static functions "min", "max" and "mean".
  2. Write a program "Stats" which is called with floating point numbers as command-line parameters, and which computes their minimum, maximum and average, using your library StdStats.
  3. For example, "Stats 4 5.2" would yield min=4, max=5.2, mean=4.6.
- Parsing strings (using methods from the String class)
  1. Read a string from the command-line and determine how many space-separated parts it has.
    - Call the class "CountParts", printing out how many parts there are.
    - In order to input a string containing spaces, you need to use single quotation marks, e.g.
```
> java CountParts 'hhg   j bbnbh bvc c'
5
          
```
    - This task is very easy using the split-method of the String-class; see Section 3.1 of the book (also available here ).
    - Examples for the split-functions are there .
    - Play around with various inputs (only spaces, leading spaces, trailing spaces, ...), to better understand the behaviour.
    - Here is a solution which also shows the parts with their indices.
  2. 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.
  3. Parse a string, where you extract all digits from it, adding them up, returning their sum and the original string without these digits:
    - For example
```
> java Crossfoot 'dg08 ha ns82g40h1 '
23
"dg ha nsgh "
          
```
    - To detect whether a character is a digit, use that characters are treated as integers, and thus can be compared by "<" etc., and can be added/subtracted.
    - Here is a solution .
- Recursion (we didn't do that section from Chapter 2):
  1. Enter the program "Htree" from the book.
  2. Write a modified program "Htree2", which asks for confirmation before continuing drawing parts of the tree.
  3. Also print out appropriate messages, so that you can follow in detail the recursion.
  4. 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:
1. Four Java-files, 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 student-number (e.g., "123456"), this put into one archive, for example "123456.zip", and this archive must be send to me via e-mail.
2. 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 Java-files, one text-file).
3. I'll send you an acknowledgement, once I got your package-file.
4. To make this safer, it would be good if in your e-mail you could state the md5sum-result for your package-file (e.g., "123456.zip"). For a Windows-environment see e.g. here for how to do this (in a Linux-system, use "md5sum 123456.zip" on a command-line).
5. 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:
1. You must have tested your code (compiled it and run it).
2. Syntax errors will result in deductions.
3. Of course, false outputs will also result in deductions.
4. Use only the Java constructions presented in the lectures.
5. Anything else will result in a deduction of 50 percent! (The same will hold for the second coursework.)
6. This is to make sure that you really concentrate on the essentials, and don't copy-and-paste code (which usually contains a lot of noise).
7. Compared to the book, we introduced a few extensions in the lectures, most important the final-qualifier, which you are expected to use.
8. Also some input checking (as discussed in the lectures) is important.
9. Take care about precise class- and file-names.
10. Choose good variable-names.
11. Provide a well-organised indentation.
12. 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
1. Sort4
2. ModularPower
3. DiscreteLogarithm
4. 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:
1. This programs takes four integers as parameters, and returns them in sorted order.
2. 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
      
```
3. Notice that in the non-error case there is no text output, just the 4 numbers, separated by a space, closing with end-of-line.
4. An additional requirement concerns the number of comparisons used by your program: for each input-sequence, only at most 5 comparisons are to be used!
5. 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.
1. The remaining three exercises concern "modular arithmetic".
2. A "modulus" n is given, a natural number greater zero.
3. Recall that for an integer x the Java operation "remainder", i.e., x % n, produces a natural number from 0 to n-1 (inclusive).
4. 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
      
```
5. In this way one keeps all numbers small.
6. Arithmetic modulo 2, the first non-trivial case, is the the arithmetic of even and odd.
7. 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.
8. 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
      
```
9. A final remark: Due to the deficient handling of negative numbers in Java w.r.t. the remainder-operation, we only consider non-negative integers here.
Specification of ModularPower:
1. This program takes three integer parameters a, e, n, and computes a^e mod n (the power of a to e, modulo n).
2. The exponent e is not directly part of the modular arithmetic (it is not reduced by the remainder operation), and we only consider non-negative e.
3. Recall that a^0=1 for all a (and thus also 0^0 = 1).
4. Since for n=1 (computing modulo 1) we have "0=1", in that special case it means 0^0 = 0.
5. 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
      
```
6. Note that in the non-error case just a number is output.
Specification of DiscreteLogarithm:
1. This program takes three integer parameters a, b, n, and computes the smallest exponent 0 <= e < n with b^e = a mod n.
2. That is, the "discrete logarithm" of a to base b modulo n.
3. It is the inverse of ModularPower.
4. In case there is no e, the result shall be "-1".
5. 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
      
```
6. Note that, again, in the non-error case no text is output.
Specification of ElementOrder:
1. 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.
2. Note that the result is always between 1 and n (inclusive).
3. 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:

Here you have the directory with all files.
The four Java-files
are the solutions to the four tasks.
There are also files "TestcasesXXX", which contain on one line the command-line parameters, and on the next line the expected output.

Second coursework: Tic-Tac-Toe (generalised)

Formal requirements:

Deadline for submission is 14/12/2011, 15:00.
This coursework has to be submitted electronically:
1. All the java-files which constitute "GeneralisedTicTacToe", together with a file "Comments.txt" have to be put into a directory named by just your student-number (e.g., "123456"), this put into one archive, for example "123456.zip", and this archive must be send to me via e-mail.
2. 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 java-files and the text-file.
3. I'll send you an acknowledgement, once I got your package-file.
4. To make this safer, it would be good if in your e-mail you could state the md5sum-result for your package-file (e.g., "123456.zip"). For a Windows-environment see e.g. here for how to do this (in a Linux-system, use "md5sum 123456.zip" on a command-line).
5. 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 machine-playing functionality.
Good coding quality is paramount:
1. You must have thoroughly tested your code -- compiled it and run it often!
2. Use only the Java constructions presented in the lectures.
3. Anything else will result in a deduction of 50 percent!
4. This is to make sure that you really concentrate on the essentials, and don't copy-and-paste code (which usually contains a lot of noise).
5. Compared to the book, we introduced a few extensions in the lectures, most important the final-qualifier, which you are expected to use.
6. Input checking (as discussed in the lectures) is important.
7. Take care about precise class- and file-names (if you have to introduce new classes; this is only needed if you add capabilities for computer-play).
8. Choose good variable-names.
9. Provide a well-organised indentation.
10. Finally, follow precisely the specifications!

General overview:

We implement the game "Tic-tac-toe" (or "Noughts and Crosses"); see Wikipedia for general information.
Actually, we will consider the generalisation "K-IN-A-ROW ON AN M-BY-N 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 machine-playing.
The decomposition of this task into small tasks (via functions) is already given.
1. The code below contains all the major functions.
2. Open places are marked by "XXX" (to be filled out).
3. 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 command-line call is GeneralisedTicTacToe K M N hh/hc/ch/cc.
For example for two humans playing ordinary tic-tac-toe:
```
> 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 debug-mode 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 run-times).
In hh-mode (human-human) 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 tic-tac-toe:

> 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 java-files, 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):
1. GeneralisedTicTacToe.java: 20
2. Parameters.java: 10
3. Field.java: 20
4. Input.java: 10
5. Rows.java: 30
6. Occurrences.java: 20
The above implements only mode "hh" (human against human). For providing also computer-playing the following marks can be gained:
1. Implementing all four modes, where the computer just chooses any correct move: 30 marks.
2. If the computer sees always if the player can win immediately: additionally 10 marks.
3. 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 not-implemented-message (already provided).
Also winnings and losses must be output using the provided messages.
Some remarks on the tasks:
1. 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?
2. 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.
3. 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.
4. 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.
5. Rows.java:
  - Compute various arrays first by hand, to understand the task.
  - Regarding the two examples given in the file-header: 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, top-left to bottom-right, bottom-left to top-right) separately.
  - It is all rather simple, it only needs some organised thinking, to create a scheme for the creation of the various row-types.
  - Use asserts!
6. 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!

Reading

Oliver Kullmann

Last modified: Wed Jan 18 17:00:49 GMT 2012