CS-M41 Programming in Java 2009/10 CS-M41 Programming in Java 2009/10 Messages A solution is provided for coursework II. If you want to get special feedback on coursework II, you can of course always come to my office, but I will definitely be in my office Friday, 22/1/2010, from 13:00 - 15:00. General information First week (22/9/2009 - 25/9/2009): Lectures 11:30 - 13:30 in the Robert Recorde room. Lab sessions from 14:00 - 16:00 in the Linux lab (room 217). From 28/9/2009 to 4/12/2009: Friday, 11-12 the lecture takes place in the Robert Recorde room. Friday 13-14 we have the lab session (in the Linux lab). The role of the lab sessions: Active participation in all lab session is awarded 10% of the overall module marks. For each lab sessions tasks are distributed, related to the accompanying lecture (from the same day). During the 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 lab sessions. Roughly in week 4 and week 7 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. 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 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. Slides The additional programs you find here . Week 0: Tuesday: Section 1.1 First programs . Here some remarks and corrections. Wednesday: Section 1.2 Data types Thursday and Friday: Section 1.3 Program flow . Here some remarks and corrections. Week 1, Friday 2/10/2009: Section 1.4 Arrays . Week 2, Friday 9/10/2009: Section 1.5 Input and output . And see here for the input-output library we will use from now on. 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. Additional material you find here. Week 3, Friday 16/10/2009: Section 2.1 Functions . Week 4, Friday 23/10/2009: Still Section 2.1 Functions . Friday, 30/10/2009: no lecture (but there is a lab session). Week 5, Friday 6/11/2009: How to write a program (or, "How to write the Poker-program") Week 6, 13/11/2009 (11-12): Section 2.2 Libraries and Clients Week 7, 13/11/2009 (14-15): Section 2.3 Recursion Week 8, 20/11/2009: Section 3.1 Data Types 1 See here for the programs discussed in the lecture. Week 9, 27/11/2009: Section 3.2 ("Creating Data Types") Data Types 2 See here for the programs discussed in the lecture. Week 10, 4/12/2009: The extended Poker package -- an example for concrete class design. Week 11, 11/12/2009: Section 3.3 Designing Data Types Additionally from 14-15 on 11/12/2009 we have a revision and exam-preparation lecture for discussing how to continue, what to expect in the exam, ... In January we have an additional exam preparation lecture (date and time to be announced). Lab sessions Remark: If some answer is already given, then understand why this is the correct answer. Week 0: Tuesday: The Exercises from Section 1.1 (see here at the bottom, Exercises 1 - 5). Wednesday: Enter the five programs from the lecture, 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, ...). You might also have a look at the improved programs. After you did this for some time, consider the exercises from Section 1.2 (see here at the bottom, 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. Thursday: 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 a better version of "TenHellos.java" (printing "Hello World!" ten times), using a while-loop. 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. Friday: 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)*(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. Consider exercises 1.3.8 - 1.3.31 from the book (see here). See here for solutions. Week 1, Friday, 2/10/2009: Enter program "Deck" from the lecture, understand it, run it. Write another program, which uses only a deck of 32 cards, where the ranks do not include 2 up to 6. Now combine both programs into one, where via a command-line argument it is decided whether 32 or 52 cards are to be used. Consider exercises 1.4.1 - 1.4.5 from the book (see here). Consider exercise 1.4.35 from the book (see here). Week 2, Friday, 9/10/2009: Today we want mainly learn how to use the three libraries StdIn.java, StdOut.java, and StdDraw.java. Write programs "RandomSeq" for printing out a sequence of N random floating-point numbers (to standard output), and "Average" for reading floating-point numbers from standard input and computing their average. Play a bit around with redirecting input and output, and pipe the two programs together. Consider exercises 1.5.1 - 1.5.3 from the book: 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 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. 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! Write program "SinFunction" that plots the function sin(4x)+sin(20x) (see the lecture script). If you have still time, or as a little home work, 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). Week 3, Friday, 16/10/2009: 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 4, Friday, 23/10/2009: If you didn't finish the exercises from last week, you might finish them now. Consider exercises 2.1.18, 2.1.19 and 2.1.20 from the book (see here). Friday, 30/10/2009: This lab session is for catching up! No new exercises --- please consider the exercises from previous weeks you didn't do. Functions are very important, so also if you are doing exercises from previous weeks not involving functions, do them now with functions. Week 5, Friday, 6/11/2009: 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, and returns integers from 0 to 3 if the string 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 . Counting random events: Write a program (class) "RandomNumbers" which takes two command-line 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 integer-array of size M for performing the counting. Here is the solution . Week 6+7, Friday 13/11/2009: 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 command-line 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. Recursion: Enter the program "Htree" from the lecture. 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 . Week 8, Friday, 20/11/2009: Use 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 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. 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. 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. 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 ). Week 9, Friday, 27/11/2009: 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 . 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"; again, play a bit around with it, and write your own clients of class Turtle, creating some simple turtle-graphics. Week 10, Friday, 4/12/2009: Understanding the (new) Poker class-collection: Add to the Card-class a test-function (that is, a "main"-function) which creates a couple of cards using the two constructors and prints them out. Here is a possible solution . Extending the analysis capabilities: Copy Poker.java to PokerExtended.java (and, of course, update the class-name accordingly). Now for the case N=0 (where an input-hand is to be analysed), add code to show for the 1+5+10=16 exchange possibilities what is the best and the worst case which could arise. Hint: You just need to apply the given capabilities. Evaluation is done by class "Evaluation" (for no big surprise). Here is the extended version . Note that this program compiles, but it cannot run succesfully until you implement the missing functionality. Week 11, Friday, 4/12/2009: Using and changing some data type. Consider Storage.java from the Poker class-collection (available here ). First you need to understand the API; so try to understand the public members of this class. Some examples for using this class are already given in the test function. Write a client program which takes N from the command-line, stores the products i*j for 1 <= i < j <= N in a Storage-object, and outputs the Storage-object. Now change the implementation (only(!) --- not the interface!), by just using a two-dimensional array (instead of the one-dimensional array as we have it now). For that you just need to change the implementations of the constructor and of the get/set-functions, and, of course, the definition of the instance-variable "results". The function "index" is no longer needed. The main-function as well as your client must work as before, without any need for changing the code, and without changes in the observable behaviour. Recall that a two-dimensional integer array is declared via, e.g., int[][] a;, initialised via, e.g., a = new int[3][4]; , and used by, e.g., a[2][3] = 77. Remark on this alternative implementation: It uses more memory, but access is quicker, since no index-computations are necessary. This is a typical situation, using different implementations for trading time versus space. Since we cannot use inheritance yet, usage of the two implementations is a bit clumsy, since we need to have two files "Storage.java" somewhere (containing the two implementations), and then to copy one or the other into the directory with our application. Inheritance allows one to define one "interface class" "Storage", which is abstract, and then to define various classes implementing this interface, like "StorageFast" and "StorageSmall". Final remark: Of course, for coursework II only the original files are to be used (though it will also work with the alternative implementation, of course). Here is the solution (see the sub-directories for old and new versions of Storage.java). Altogether 4 programs can be compiled and run: The two Storage-programs ("New" and "Old", each with its test-program). The two versions of the Client-program, using the two versions of the Storage-class. See the files for how to compile and run these four programs. Coursework First coursework A program "Poker.java" has to be written, consisting of the class "Poker", and this file has be sent via e-mail to me (just a single file). You are encouraged to use the libraries StdIn and StdOut (you don't need to include them in your submission). This program shall take one command-line argument N. For N=0 the following should happen: A hand of (five) cards is read from standard input, where each card comes in the form "Jack of Clubs" etc. (as we had it in the example from the lecture). Additional spaces (or space symbols like end-of-line symbols or tab-symbols) must not matter. The names of suites (for input) are "Clubs, Diamonds, Hearts, Spades". The names of the card ranks (for input) are "2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace". The program then determines which of the following nine standard hand ranks (in order from highest to lowest) Straight flush (a straight and a flush -- see below) Four of a kind (four equal card ranks) Full house (two equal card ranks together with three equal card ranks) Flush (all cards of same suit) Straight (cards in rank order, where the ace can be used as the lowest or the highest card rank) Three of a kind (three equal card ranks) Two pairs (two times two equal card ranks) One pair (two equal card ranks) High card (none of the above). applies for the hand, where in case of several possibilities the higher rank has to be output. For N > 0 the program chooses itself N random hands, counts how often each of the above hand ranks occurs, and outputs the relative frequency of each rank, that is, the quotients (number of occurrences) / N. You need to determine for which N the values are really close to the correct probabilities, and in a comment in your program you need to show such N and the output produced by your program. This archive contains examples --- your program must be able to classify all these hands correctly. Very important: Your program must compile. Your program must run. It must produce correct results. Try to give good error messages in case some user input is wrong. Use good variable names. Declare variables as local as possible. Use many functions. Specify the meaning of functions and important variables via comments. Important: The program must be written solely by you! I won't accept any two similar programs. If you do not implement the full functionality (for example, you cannot determine all hand ranks), then please state this clearly in your comments. Hints: Every non-trivial program has to be first designed on paper. Of fundamental importance is to determine how to handle the various object classes! Here we have "suites", "card ranks", "cards" (a combination of suit and card rank), "hands" (five cards) and "hand ranks". Perhaps you find it useful to use additional object classes. Strings are not appropriate data types (except for input and output). Best is to use codes, like 1 .. 52 for the cards, 1 .. 4 for the suites, 1 .. 13 for the card ranks, and 1 .. 9 for the hand ranks. One could represent cards as pairs of suit and card rank, but yet we don't have the appropriate means for doing so, and using codes 1 .. 52 is easiest. You can use modular arithmetic to handle these codes somewhat more elegantly, but this is not needed. Hands (of cards) are represented as arrays (of five cards). Provide functions for extracting the suit-code and the card-rank-code from a card-code. When reading cards from (standard) input, you read in single strings, and then you need to compare the input string objects to given strings in order to compute the codes. Use the member function "String.equals" for that. Thus provide functions which convert strings for card ranks and strings for suites to the respective codes. Conversely you need functions which convert codes into the strings. As said before, don't use strings for computations, but only for input and output. All computations are best performed using "mathematical" representations of the objects, suitable for computation. Strings are just means for input and output, except, of course, the computations are actually computations on strings, as in text or word processing. Here is a model solution . Second coursework Now we play poker (the simplest version). Deadline is Monday, 21/12/2009; submission as before via e-mail. The code must be written in all parts solely by you (otherwise zero marks are the result, potentially followed by disciplinary actions). This time you need to add code to a couple of files; send me an archive of the changed files, plus an additional file named "StudNumber_Coursework_2.txt" (plain text), where you state your name (while the student number is in the name of that file), and where you state and explain the places where you added code. Reminder: As usual with electronic submission, your submission of coursework implicitly contains your signature under the following standard phrase from the Coursework Submission Form: I am aware of the University policy on unfair practice and I certify that this coursework is the result of my own independent work except where otherwise stated, and that all other sources are explicitly acknowledged. We only consider a simple form of "draw poker": After the cards are dealt, the player can choose up to 2 cards to be exchanged. After exchange, all hands are shown (we do not do betting), and the winner is determined. We only consider two players. The task is to complete the framework, to devise some strategies for card exchange, and to play a tournament with your strategies, determining what works best. No classes (from the Java library or elsewhere) may be used except those provided with the coursework. The code is only to be changed at the marked places (you find "XXX" there), while the rest must remain untouched. Here are the files you need to consider. Your first task is to study the code carefully! You need to understand (and partially reconstruct) the API of all classes. To get into it, start considering Poker.java : This implements the functionality from the first coursework, now using the new framework. Additionally, while in the first coursework only the "major ranking" of hands into the nine major poker ranks has been considered, now the complete ranking is provided. So now there are 6331 hand ranks (while there are 9 major hand ranks): A hand wins against another hand if and only if its hand rank is (strictly) better, that is, numerically lower, than that of the other hand. "java Poker 0" works already, but "java Poker N" for N>0 doesn't work yet, since you have to complete first the Bank-implementation. The code here using Bank is one example for the usage of this class, which you can study, in order to find out what precisely is the API for the Bank-class (in this case). The places where functions have to be completed are the following (NOW (22/1/2010) these files contain already the solutions): Bank.java : functionality regarding dealing and exchanging cards. Evaluation.java : computing all possible outcomes for one exchange request. TwoPlayers.java : Using all available strategies for one play between two players, and determining the results. Tournament.java : the main program, letting the strategies play against each other for many rounds, and displaying the results. Completing this functionality can is worth roughly 50-60% of the coursework, while the rest is earned by implement various exchange strategies in Strategy.java . It is your task to determine the precise specifications for all these places. If needed, you may add new private member functions, but no data member (static or non-static) shall be added, and none of the existing code is to be altered. You will find there already certain code-fragments and hints, to get you started. This exercise is about DESIGN: Yet you cannot create larger systems (with good design), and so the framework is given to you, and you have to grasp it, and to complete it. And regarding the strategies, you can show some creativity. Until Monday, 7/12/2009, there might occur some (small) changes in the framework (if it makes the task easier). In the lecture next Friday (4/12/2009) certain key elements of the framework will be discussed. Links A Git repository is available, where you can download the source code repository. There you also find C++ versions. Reading Oliver Kullmann Last modified: Fri Jan 22 12:14:47 GMT 2010
