Com S 228 --- Introduction to Data Structures HOMEWORK 1: SCHEME TO C++ (File $Date: 1995/01/30 02:24:20 $) Due: problem 3 is due in your discussion section the week of January 26, problems 4 and 7 are due on January 30 at the beginning of class (unless you are in the Friday at 8am section, in which case problem 3 is due on Jan 30, and problem 7 is due on Feb 6., and the other due dates are unchanged.) In this homework, you will learn some basics of C++ programming. The first few problems of this homework are suggested practice with syntax of expressions. Then we move into some small problems dealing with conditional statements and loops. For this homework, don't use recursion for any solution. (And of course, your solutions are to be written in C++.) Each file you print should have the file name and your information (your ~/.me file as in HW0) at the top. Use comments as we are doing in class; we won't be making a big deal out of these comments yet, but if you want more information, see Headington and Riley's Appendix D for details. For additional practice, we suggest that for at least some of the problems, you write out a solution on paper first. This is more like what the test will be. When you are happy with your paper version, try it on the computer. (Note that you must hand in a printout and a transcript, however.) In this and following homeworks, we'll have section headings which are the readings associated with particular problems. They appear below. TRANSLATIONS FROM SCHEME TO C++ (Handout), HEADINGTON & RILEY: APPENDIX A.1-6 and A.8-13, and DEITEL & DEITEL: 1.6-7, 1.17-19 (If you don't know Scheme, don't panic. If you know the language C instead of Scheme or Pascal, then read Appendix B instead of A in Headington and Riley's book.) 1. (suggested practice) Do some of the exercises in the self-review section of Deitel & Deitel's book. I suggest that exercises 1.3-8 on pp. 42-3 might be useful. Do what parts seem useful to you, then look on page 44 for answers. (You certainly don't have to do all of these.) 2. (suggested practice) Do one or more of exercises 1.20-25 of Deitel & Deitel's book. (It's possible to check your answers using the computer.) 3. (30 points) Do exercise 1.26 in Deitel & Deitel's book. If the three numbers entered are all equal, they are both largest and smallest. Bring in a printout of your program and a transcript of testing (as always). For grading this problem, you'll get full credit for handing it in during your discussion section. (The usual late policy applies). In your discussion section, you'll discuss your solution with another class member, which is all the feedback you'll get. Be sure to write your program clearly. (This is called a "code-walkthrough" in industry.) We won't check the details of your work, as that will be the subject of the discussion. So don't worry if it doesn't work exactly right. We will check that what you hand in has the right parts (a printout of each file, labeled correctly with comments at the top, and a transcript). 4. (60 points total) James Gleick's book, Chaos: Making a New Science (Penguin Books, 1987), describes the emerging science of ``chaos theory,'' which is largely concerned with nonlinear systems. An early inspiration for chaos theory comes from biology. (See pages 62-64 of Gleick's book.) Biologists use the ``logistic difference equation'' to model the growth of a population over time. For simplicity, one can represent a population, say of fish in a pond, as a (floating point) number between 0.0 and 1.0. The number 0.0 represents extinction, while 1.0 represents the greatest conceivable population of fish that will fit in the pond. A simple linear function, L(x) = r * x, that gives the population for the next year in terms of the current year's population, x, is inadequate, since it does not take limited resources into account. Instead, some biologists in the 1950s started to use a non-linear equation: the logistic difference equation: P(r,x) = r * x * (1-x) This equation gives next year's population, P(r,x), in terms of this year's population, x, a parameter, r that represents the amount of ``nonlinearity'', and a factor 1-x that keeps the population from getting too big. For example, suppose r is 2.7 and the population at year 0 is 0.02. Then the population at year 1 is 0.05292 = 2.7 * 0.02 * (1 - 0.02). The population at year 2 is about 0.1353. If you keep computing, you'll see that the population eventually reaches an equilibrium of about 0.6296. To describe the process more concisely, I'll introduce a bit of notation. The notation is for iterations of a two-argument function, P. Let P^(0)(r,x) = x, and for all integers, k > 0, let P^(k)(r,x) = P(r, P^(k-1)(r,x)). For example, P^(0)(2.7,0.02) = 0.02, and P^(1)(2.7,0.02) = P(2.7, P^(0)(2.7,0.02)) = P(2.7, 0.02) = 0.05292. Similarly, P^(2)(2.7,0.02) = P(2.7, P^(1)(2.7,0.02)) = P(2.7, P(2.7, P^(0)(2.7,0.02))) = P(2.7, 0.05292) = 0.1353 Therefore, the claim about equilibrium being reached for the situation described in the previous paragraph can be expressed in this notation as follows: ``for sufficiently large k and for x > 0, P^(k)(2.7,x) is approximately 0.6296''. Does iterating the logistic difference equation always converge on an equilibrium population? Surprisingly, the answer is no! This is what you will investigate in this problem. a. (15 points) Write a function, that satisfies the following specification. Note that FCTVAL means "the value returned by this function". (See Headington and Riley's appendix D, p. A-116, for details.) double logistic_diff(double r, double x) // PRE: 0.0 < x < 1.0 and 0.0 < r < 4.0. // POST: FCTVAL is P(r,x), which is the value of the logistic // difference equation for r and x. Put the function logistic_diff in the file logistic.C. Also write a main program, in file chaos_a.C, that prompts for r and x, and prints the result of calling logistic_diff(r, x). (Such a main program is called a "test harness".) A sample dialog is as follows r? 2.7 x? 0.02 P(2.7, 0.02) is 0.05292 (Your output for this example might be slightly different, as floating point arithmetic is not exact; we also won't worry about the formatting so much. For example, it's okay if your output for this example is P(2.7, .02) is .0529196 or something else similar. If you must fuss with it, look at DD 11.7.6.) Do a printout and testing for this part, first, then go on to the next part. You might want to use a separate directory and edit a copy of the program, in case you decide you want to come back and change this part. b. (20 points) Add error checking to your main program. That is, print on cerr a message such as "logistic_diff: bad value for x: 25.01" if x is too large, and a similar message for x being too small or large. This makes the specification for the main program as follows. int main() // MODIFIES: cin, cerr, cout // POST: prompt for two numbers r and x; // if 0.0 < x < 1.0 and 0.0 < r < 4.0, then print the // value of the logistic difference equation on cout // and return with FCTVAL == 0, // otherwise print an error message on cerr and return with // FCTVAL == 1. (Hint: you can use other functions if you wish, but be sure to document them with PRE and POST comments.) Call the main program chaos_b.C, and hand in a printout and testing for this part. (You can use the Unix command echo $status at the Unix prompt to test the return value of a program.) c. (25 points) Make another version of your program, chaos_c.C, which prompts for and inputs 3 numbers: the doubles r and x, and also an int, k. In addition to the error checking for r and x, as in part b above, your program should also check that k is not negative; if k is negative, print an informative error message and return with FCTVAL == 2. Otherwise, the program should print the values of P^(0)(r,x), P^(1)(r,x), ..., P^(k)(r,x) in the format shown in the following example dialog. (Again, your exact numeric results and formatting may differ slightly.) r? 2.7 x? 0.02 k? 2 P^(0)(2.7, 0.02) is 0.02 P^(1)(2.7, 0.02) is 0.05292 P^(2)(2.7, 0.02) is 0.1353 This makes the specification of the program as follows. int main() // MODIFIES: cin, cerr, cout // POST: prompt for three numbers r, x, and k; // if 0.0 < x < 1.0 and 0.0 < r < 4.0 and 0 <= k, then print the // value of the iterates P^(0)(r,x), P^(1)(r,x), ..., P^(k)(r,x) // of the logistic difference equation on cout // and return with FCTVAL == 0, // otherwise print an error message on cerr and return with // FCTVAL == 1 (if r or x are in error) // or FCTVAL == 2 (if k is in error), // and either FCTVAL == 1 or FCTVAL == 2 if k and one or more of r // and x are in error. In your testing for this problem, use your program to try larger and larger numbers for r. Don't start with 3.98; start smaller, say around 2 and increase slowly so you can see what happens. Remember that you are *not* to use recursion for this problem. Instead try using auxiliary variables and a loop of some kind. 5. (10 points; extra credit) This continues problem 4c. You can write your answers on paper for this. a. For what values of r do the iterates no longer reach equilibrium? b. What do the iterates look like at that point? c. What happens if you keep going higher? 6. (10 points; extra credit) The precondition of logistic_diff says that r must be between 0 and 4. Derive this condition mathematically. (Hint: use differential calculus.) 7. (20 points) Write a makefile for compiling your code for problem 4c above. Hand in a printout of your makefile, and a transcript showing how you tested it. Call the executable program chaos_c.exe.