Take-home labs are graded to provide you with feedback. However, the marks do not contribute to your final grade. Instead, one mark (attempt-mark) is awarded for each assignment -- and this mark goes into the computation of your final grade -- on the following conditions:
This lab requires you to do two exercises. The third exercise is for your own practice and you do not need to submit it.
You are advised to review the material covered in chapters 1 through 6 and read Programming Style, Design and Marking Guidelines before attempting this lab assignment. You should not use syntax or constructs not yet covered in lectures; you shouldn't need to and may even be penalized for doing so (if the objective of the assignment is undermined). If in doubt, please ask for clarification in lecture or in the IVLE discussion forum.
Remember to spend some time thinking about the algorithm for each exercise and write out the pseudo-code on your own before you start typing in your program.
A word of advice: Code incrementally. Do not type in the whole program (especially when it is long) and then compile it. Instead, type your program in bits and pieces and compile it frequently. Try to maintain a compilable program even while you are working on it. Submitting a compilable program that partially works is better than submitting an un-compilable one. This last point especially applies to your sit-in labs and practical exam.
Note that:
For more information on CourseMarker, please refer to CS1101 Labs page.
For this lab, the number of submissions is set to 10. Only your last submission will be graded.
If you have any questions, you may post your queries in the IVLE discussion forum. Do not post your programs (partial or complete) in the forum before the deadline!
Define a FortuneCookie class that contains two data members: value and cookie. The value is a positive integer of type int, and cookie is a fortune cookie message.
This class contains a method sumDigits() that repeatedly adds the individidual digits in the value. If the resulting number consists of more than one digit, it repeats the process of adding the individual digits, until a single digit is obtained. This digit then determines which fortune cookie to pick.
Example: assuming that the value is 678934598. The first round of summing up the digits gives 6+7+8+9+3+4+5+9+8 = 59. As the answer 59 contains more than one digit, we repeat the process: 5+9 = 14. It still contains more than one digit, so we repeat: 1+4 = 5. The final answer is 5, and a corresponding fortune cookie is picked.
You are to write an application program Lab3Ex1.java that reads in an integer, creates a FortuneCookie object and assigns the correct cookie message into the object, and then display the cookie message.
The skeleton programs FortuneCookie.java and Lab3Ex1.java are given. FortuneCookie.java uses array which is not covered in class yet.
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first three lines (in green) below are commands issued to compile and run your Java programs if you are using in-line commands, for example, on UNIX. If you are not, you may ignore them.
$ javac FortuneCookie.java $ javac Lab3Ex1.java $ java Lab3Ex1 Enter number: 678934598 A cheerful message is on its way to you.
Another sample run:
$ java Lab3Ex1 Enter number: -9 Enter number: 0 Enter number: 123 A well-aimed spear is worth three.
Submit your programs FortuneCookie.java and Lab3Ex1.java through CourseMarker.
Numerical analysis is an important area in computing. One simple numerical method we shall study here is the Bisection method, which computes the root of a continuous function. The root, r, of a function f is a value such that f(r) = 0.
How does bisection method work? It is best explained with an example. Given this polynomial p(x) = x3 + 2x2 + 5, we need to first provide two endpoints a and b such that the signs of p(a) and p(b) are different. For example, let a=-3 (hence p(a)=-4) and b=0 (hence p(b)=5).
The principle is that, the root of the polynomial (that is, the value r where p(r) = 0) must lie somewhere between a and b. So for the above polynomial, the root r must lie somewhere between -3 and 0.
This is achieved as follows. The bisection method finds the midpoint m of the two endpoints a and b, and depending on the sign of p(m) (the function value at m), it replaces either a or b with m (so m now becomes one of the two endpoints). It repeats this process and stops when one of the following two events happens:
Figure 1 below shows the two endpoints a (-3) and b (0), their midpoint m (-1.5), and the function values at these 3 points: p(a) = -4, p(b) = 5, p(m) = 6.125.
Since p(m) has the same sign as p(b) (both values are positive), this means that m will replace b in the next iteration.
Figure 1. Graph of p(x) = x3 + 2x2 + 5
The following table illustrates the iterations in the process. The end-point that is replaced by the mid-point value computed in the previous iteration is highlighted in pink background.
| iteration | endpoint a | endpoint b | midpoint m | function value p(a) | function value p(b) | function value p(m) |
| 1 | -3.000000 | 0.000000 | -1.500000 | -4.000000 | 5.000000 | 6.125000 |
| 2 | -3.000000 | -1.500000 | -2.250000 | -4.000000 | 6.125000 | 3.734375 |
| 3 | -3.000000 | -2.250000 | -2.625000 | -4.000000 | 3.734375 | 0.693359 |
| 4 | -3.000000 | -2.625000 | -2.812500 | -4.000000 | 0.693359 | -1.427002 |
| 5 | -2.812500 | -2.625000 | -2.718750 | -1.427002 | 0.693359 | -0.312714 |
| 6 | -2.718750 | -2.625000 | -2.671875 | -0.312714 | 0.693359 | 0.203541 |
| 7 | -2.718750 | -2.671875 | -2.695312 | -0.312714 | 0.203541 | -0.051243 |
| 8 | -2.695312 | -2.671875 | -2.683594 | -0.051243 | 0.203541 | 0.076980 |
| 9 | -2.695312 | -2.683594 | -2.689453 | -0.051243 | 0.076980 | 0.013077 |
| 10 | -2.695312 | -2.689453 | -2.692383 | -0.051243 | 0.013077 | -0.019031 |
| 11 | -2.692383 | -2.689453 | -2.690918 | -0.019031 | 0.013077 | -0.002964 |
| 12 | -2.690918 | -2.689453 | -2.690186 | -0.002964 | 0.013077 | 0.005059 |
| 13 | -2.690918 | -2.690186 | -2.690552 | -0.002964 | 0.005059 | 0.001048 |
| 14 | -2.690918 | -2.690552 | -2.690735 | -0.002964 | 0.001048 | -0.000958 |
| 15 | -2.690735 | -2.690552 | -2.690643 | -0.000958 | 0.001048 | 0.000045 |
| 16 | -2.690735 | -2.690643 | -2.690689 | -0.000958 | 0.000045 | -0.000456 |
Hence the root of the above polynomial is -2.690689 (because the difference between a and b in the last iteration is smaller than the threshold 0.0001), and the function value at that point is -0.000456, close enough to zero.
(Some animations on the bisection method can be found on this website: Bisection method. Look at the first one.)
Write a program Bisection.java that asks the user to enter the integer coefficients (c3, c2, c1, c0) for a polynomial of degree 3: c3*x3 + c2*x2 + c1*x + c0. It then asks for the two endpoints, which are real numbers. You may assume that the user enters a continuous function that has a real root. You may use the double data types for real numbers. To simplify matters, you may also assume that the two endpoints the user entered have function values that are opposite in signs.
In the output, real numbers are to be displayed accurate to 6 decimal digits (see output in sample runs below).
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green) below are commands issued to compile and run your Java programs if you are using in-line commands, for example, on UNIX. If you are not, you may ignore them.
Only the last 2 lines shown in bold purple are what your program needs to produce. The iterations are shown here for your own checking only.
The sample run below shows the output for the above example. Note that the iterations end when the difference of the two endpoints is less than 0.0001, and the result (root) is the midpoint of these two endpoints.
$ javac Bisection.java
$ java Bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 1 2 0 5
Enter endpoints a and b: -3 0
#1: a = -3.000000; b = 0.000000; m = -1.500000
p(a) = -4.000000; p(b) = 5.000000; p(m) = 6.125000
#2: a = -3.000000; b = -1.500000; m = -2.250000
p(a) = -4.000000; p(b) = 6.125000; p(m) = 3.734375
#3: a = -3.000000; b = -2.250000; m = -2.625000
p(a) = -4.000000; p(b) = 3.734375; p(m) = 0.693359
#4: a = -3.000000; b = -2.625000; m = -2.812500
p(a) = -4.000000; p(b) = 0.693359; p(m) = -1.427002
#5: a = -2.812500; b = -2.625000; m = -2.718750
p(a) = -1.427002; p(b) = 0.693359; p(m) = -0.312714
(... omitted for brevity ...)
#15: a = -2.690735; b = -2.690552; m = -2.690643
p(a) = -0.000958; p(b) = 0.001048; p(m) = 0.000045
#16: a = -2.690735; b = -2.690643; m = -2.690689
p(a) = -0.000958; p(b) = 0.000045; p(m) = -0.000456
root = -2.690689
p(root) = -0.000456
The second sample run below shows how to find the square root of 5. For polynomial where there are more than one real root, only one root needs to be reported.
$ java Bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 0 1 0 -5
Enter endpoints a and b: 1.0 3.0
#1: a = 1.000000; b = 3.000000; m = 2.000000
p(a) = -4.000000; p(b) = 4.000000; p(m) = -1.000000
#2: a = 2.000000; b = 3.000000; m = 2.500000
p(a) = -1.000000; p(b) = 4.000000; p(m) = 1.250000
(... omitted for brevity ...)
#16: a = 2.236023; b = 2.236084; m = 2.236053
p(a) = -0.000201; p(b) = 0.000072; p(m) = -0.000065
root = 2.236053
p(root) = -0.000065
The third sample run below shows how to find the root of the function 2x2 - 3x. Since the midpoint of the given endpoints a and b is 1.5 which is the root of the function, the loop ends after the first iteration.
$ java Bisection
Enter coefficients (c3,c2,c1,c0) of polynomial: 0 2 -3 0
Enter endpoints a and b: 0.5 2.5
#1: a = 0.500000; b = 2.500000; m = 1.500000
p(a) = -1.000000; p(b) = 5.000000; p(m) = 0.000000
root = 1.500000
p(root) = 0.000000
Submit your program Bisection.java through CourseMarker.
In Lab #2 Exercise 2, the program asks for only two lines of instructions from the user. Since you have learned repetition statements, you may enhance your program by asking the user to enter as many instructions as he/she wishes.
This is for your own practice hence you do not need to submit your program.
The deadline for submitting all programs is 28 September 2009, Monday, 23:59hr. Late submissions will NOT be accepted.