(*^ ::[ Information = "This is a Mathematica Notebook file. It contains ASCII text, and can be transferred by email, ftp, or other text-file transfer utility. It should be read or edited using a copy of Mathematica or MathReader. If you received this as email, use your mail application or copy/paste to save everything from the line containing (*^ down to the line containing ^*) into a plain text file. On some systems you may have to give the file a name ending with ".ma" to allow Mathematica to recognize it as a Notebook. The line below identifies what version of Mathematica created this file, but it can be opened using any other version as well."; FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2"; MacintoshStandardFontEncoding; fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e8, 24, "Times"; fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, e6, 18, "Times"; fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times"; fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, a20, 18, "Times"; fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times"; fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times"; fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; fontset = input, noPageBreakInGroup, preserveAspect, groupLikeInput, M42, N23, bold, B65535, L-5, 12, "Courier"; fontset = output, output, inactive, noPageBreakInGroup, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; fontset = message, inactive, noPageBreakInGroup, preserveAspect, groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier"; fontset = print, inactive, noPageBreakInGroup, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; fontset = info, inactive, noPageBreakInGroup, preserveAspect, groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier"; fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, 12, "Courier"; fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, 10, "Geneva"; fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = leftheader, inactive, L2, 12, "Times"; fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7, 12, "Times"; fontset = leftfooter, inactive, L2, 12, "Times"; fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 10, "Times"; fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, 12, "Times"; currentKernel; ] :[font = smalltext; inactive; preserveAspect] Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will. Free for distribution to college and university instructors for personal, non-commercial use. If these notebooks are used in a course, the authors request $20 per student. :[font = title; inactive; preserveAspect] Chapter II. List-Based Programming :[font = title; inactive; preserveAspect] 4. Introduction to Lists and Using Programming Principles :[font = text; inactive; preserveAspect] [Note to instructor: if the number of students is changed, numbers in this lab must be changed. 15 may not be appropriate for the number of questions asked per day, and at one point later in the lab a prediction about an average is made which will depend on "numStuds". See also the homework. This caveat is duplicated in the second section below.] :[font = smalltext; inactive; preserveAspect] Last revision: September 5 1996 :[font = text; inactive; preserveAspect] In this section we introduce two methods of approaching a problem and use one of them to implement a class roster and answer some probabilistic questions. In doing so, we introduce list and list manipulations when necessary. :[font = section; inactive; Cclosed; preserveAspect; startGroup] Problem Solving Strategies (Bottom-Up, Top-Down) :[font = text; inactive; preserveAspect] Computer programming tasks, while sometimes simply stated, frequently involve using many steps in their solution. These steps are sometimes each completed once, in order, and at other times some of the steps in the solution are repeated. In this lab we will consider both situations, and, in doing so, will give you some hands-on experience with the solution to a programming problem. Before we reach the details, however, a few remarks about the method we will use in approaching the task are in order. After all, when we are presented with a homework problem, we often confront the questions "Where do we start?" and "How do we proceed?" :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Bottom-Up Analysis :[font = text; inactive; preserveAspect; endGroup] The phrase bottom-up analysis refers to approaching a problem from the inside out or from small pieces to larger ones. By this we mean identifying within the larger problem small sub-tasks which we may want to perform several times, defining Mathematica functions to perform these small sub-tasks, testing these functions, and building up from there to medium-sized tasks, and so on. At each stage it is best to have a clear, concise purpose in mind for the sub-tasks and to name functions and their arguments with names reflecting their purposes. Also, there is no requirement that one simply define small functions and then put them together in one large function; instead, several intermediate steps may be appropriate. In this section we will use a bottom-up approach to solve the given problems. ;[s] 3:0,0;11,1;30,0;805,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = subsection; inactive; preserveAspect; startGroup] Top-down Analysis :[font = text; inactive; preserveAspect; endGroup; endGroup] The companion strategy to bottom-up analysis is top-down analysis, and this sort of analysis of a problem refers to the process of decomposing the larger task into a few smaller sub-tasks with clear and concise purposes, naming these functions (but not yet writing code for them), and then breaking each of these subtasks down further to even smaller ones, and naming those functions. When one reaches a function sufficiently small, it is time to write the Mathematica code for that function, and then build up from there. For extremely large problems top-down analysis can be useful in keeping the larger picture always in mind. ;[s] 3:0,0;48,1;65,0;632,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = section; inactive; Cclosed; preserveAspect; startGroup] Example of Problem Solving: A Class Roster :[font = text; inactive; preserveAspect] Execute the following input cells. :[font = input; preserveAspect] numStuds = 15; roster = {"Barrington", "Culbertson", "Edmundson", "Edwards", "Harrington", "Henry", "Krause", "Lenhart", "Medendorp", "Mileham", "Nelson", "Pfeiffer", "Sobczak", "Thomson", "Vogelbacher"}; :[font = text; inactive; preserveAspect] [Note to instructor: if the number of students is changed, numbers in this lab must be changed. 15 may not be appropriate for the number of questions asked per day, and at one point later in the lab a prediction about an average is made which will depend on "numStuds". See also the homework.] :[font = text; inactive; preserveAspect] Problem: This class has "numStuds" people on the roster. If we randomly call on people 15 times a day, there may be people who are called upon more than once. How many different people are likely to be called on? ;[s] 3:0,0;171,1;180,0;216,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = text; inactive; preserveAspect] Answer: Without some mathematics, this problem is difficult to answer theoretically. Empirically, however, we may simulate the situation and apply inductive reasoning. :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Randomly Calling On One Student :[font = text; inactive; preserveAspect] We approach the problem using simulation by first examining what small problems we can answer for ourselves. For instance, how can we select a random name from the list of names? How can we even select a particular name? :[font = text; inactive; preserveAspect] The Mathematica double-bracket notation allows us to select a particular element of the list. :[font = input; preserveAspect] roster[[5]] :[font = text; inactive; preserveAspect] This gets the fifth name in the list. To get a random name we need first to choose a random number from 1 to "numStuds" and choose that position on the roster. :[font = text; inactive; preserveAspect] To get a random Integer between 1 and "numStuds" we can use the "Random[ ]" command. The "Random[ ]" command returns a random value of the data type specified in the first argument, between the two values given in a list as the second argument. (Execute "?Random" if you are confused!) :[font = input; preserveAspect] Random[Integer,{1,numStuds}] :[font = text; inactive; preserveAspect] Putting the two together---using the result of the "Random[ ]" command inside the double-bracket notation---gives us a random name from the list. ;[s] 3:0,0;71,1;77,0;146,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = input; preserveAspect; endGroup] roster[[ Random[Integer,{1,numStuds}] ]] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Randomly Calling On Several Students :[font = text; inactive; preserveAspect] To get five random names we could enter the command above five times. A better program, however, is to use the "Table[ ]" command to get a list of all five names. Here's an example of how to use the "Table[ ]" command to a list of five "r"'s. :[font = input; preserveAspect] Table[ r, {5} ] :[font = text; inactive; preserveAspect] We want five random names, so instead of putting "r" inside the "Table[ ]" command as the first argument, we replace "r" with the expression which will produce a random name for us. The function "Table[ ]" will evaluate this expression five separate time. To make the code easier to read, we will use some indentation, which does not affect the execution. :[font = input; preserveAspect] Table[ roster[[ Random[Integer,{1,numStuds}] ]], {5} ] :[font = text; inactive; preserveAspect] How about a list of fifteen random names? :[font = input; preserveAspect; endGroup] Table[ roster[[ Random[Integer,{1,numStuds}] ]], {15} ] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Counting the Number of Distinct Students Called On :[font = text; inactive; preserveAspect] Now we know how to generate a list of fifteen random names, chosen from the list. But how many different names are on this list? We could count them by hand, but it would be helpful if we could have Mathematica throw out the duplicates. To do this, we can use the function "Union[ ]". Here's an example of the "Union[ ]" function: ;[s] 3:0,0;96,1;105,0;335,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = input; preserveAspect] Union[ {c,c,b,a,b,a,c,c,c} ] :[font = text; inactive; preserveAspect] Notice that "Union[ ]" eliminates duplicates in a list and returns a sorted list. Let's use this idea to see how many different names we have in a rando m list of fifteen names. To eliminate duplicates, we wrap "Union[ ]" around the command we're currently using to produce fifteen random names: :[font = input; preserveAspect] Union[ Table[ roster[[ Random[Integer,{1,numStuds}] ]], {15} ] ] :[font = text; inactive; preserveAspect] (We expect to be getting a different list of names each time we use the "roster[[....]]" selection operation, so don't be surprised if this list doesn't match up with the one that came before.) Now how many students are on the list? We can ask Mathematica to count the number of elements in the list by using the "Length[ ]" command. Let's test the "Length[ ]" command. :[font = input; preserveAspect] Length[ {3,3,5,5,6} ] :[font = text; inactive; preserveAspect] Yes, there are five elements in the list {3,3,5,5,6}. So, let's now wrap our list of distinct elements in the "Length[ ]" function: :[font = input; preserveAspect; endGroup] Length[ Union[ Table[ roster[[ Random[Integer,{1,numStuds}] ]], {15} ] ] ] :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Writing a Function :[font = text; inactive; preserveAspect] We now have a Mathematica program and a have provided a good example of how to write programs using Mathematica. The idea is to start with simple parts and to build up a nesting of functions to accomplish the final task. ;[s] 3:0,0;26,1;34,0;224,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = text; inactive; preserveAspect] What if we decide to repeat this experiment, drawing twenty random names instead of fifteen? One way is to just use the same command as above, replacing the {15} by {20}. But suppose we also want to see what happens when we draw 30, 40, 50, or 5 names. If we plan on performing a process many times with different values, then it's a good idea to convert the process into a function, assigning it a name and providing for any parameters. For example, if we will need to square many numbers, we should define a squaring function: :[font = input; preserveAspect] Clear[square] square[x_]:=x^2 :[font = text; inactive; preserveAspect] Remember that the "x" on the left-hand side is the formal parameter for the function, as indicated by the underscore "_". It's important that the "_" (sometimes a blank) appears on the left, but not on the right hand side. It's also a good idea to use "Clear[ ]" to erase any previous definitions of the name we are about to use. We can now use the function "square[ ]" to compute the square of anything. :[font = input; preserveAspect] square[3] square[{a,b,c}] :[font = text; inactive; preserveAspect] (Notice that we don't use the underscore here, only when we first define the function.) Now let's convert our process above into a function. We can use any name we like, but two useful guidelines are the following: (1) All built-in commands start with uppercase letters; to avoid conflicts with these, begin a name of a function with a lowercase letter; and (2) Choose a descriptive name. ;[s] 3:0,0;373,1;384,0;391,-1; 2:2,13,9,Times,0,12,0,0,0;1,13,9,Times,2,12,0,0,0; :[font = input; preserveAspect] Clear[draw] draw[n_]:=Length[ Union[ Table[ roster[[ Random[Integer,{1,numStuds}] ]], {n} ] ] ] :[font = text; inactive; preserveAspect] Now we can answer the question posed in the original problem, for any number of times the class is called upon. For a day during which the class was called upon fifteen times, we would execute :[font = input; preserveAspect] draw[15] :[font = text; inactive; preserveAspect] This command reports how many different people fielded fifteen questions. Similarly, if the class was called upon twenty-five times, we would execute :[font = input; preserveAspect] draw[25] :[font = text; inactive; preserveAspect; endGroup] This command reports how many different people fielded 25 questions. :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Approaching an Estimate :[font = text; inactive; preserveAspect] Since "draw[ ]" uses the "Random[ ]" function, we shouldn't expect to get the same answer every time. Here are ten different trials of asking fifteen questions. :[font = input; preserveAspect] Table[ draw[15], {10}] :[font = text; inactive; preserveAspect] Remember that we started by asking for an estimate of "draw[15]". Perhaps it would be a good idea to take an average of ten trials. To do this we need to sum up the results of ten trials and then divide by ten. To perform the addition, we'll need the "Sum[ ]" function, and example of which follows: :[font = input; preserveAspect] Sum[ r, {5}] :[font = text; inactive; preserveAspect] When we entered "Table[ r, {5}]" we found a list of 5 "r"'s; now, using "Sum[ ]" instead of "Table[ ]" gives us a sum of 5 "r"'s. Now let's add up ten values of "draw[40]" and divide by ten. :[font = input; preserveAspect] Sum[ draw[40], {10} ] /10 :[font = text; inactive; preserveAspect] We'll name a new function that will compute the average value of "draw[n]" over several trials; hence we'll need a second parameter, which we call "trials". While we're writing the new function, we'll wrap "N[ ]" around the expression to insure that we always have a decimal answer. :[font = input; preserveAspect] Clear[aveDraw] aveDraw[n_,trials_] := N[ Sum[ draw[n], {trials} ] / trials ] :[font = text; inactive; preserveAspect] The two arguments of our function are "n", the number of names we want to draw each time, and "trials", the number of trials over which we want to average. :[font = input; preserveAspect] aveDraw[15,100] :[font = text; inactive; preserveAspect] The command above tells us that the average number of different people called on each day will be between 10 and 11. Of course, only ten or eleven different people will actually be called upon during any given day! Is this a good answer to our original question? If we enter the same command again we're likely to get slightly different results. :[font = input; preserveAspect] aveDraw[15,100] :[font = text; inactive; preserveAspect] But if the results aren't too different, then we can feel good about giving an estimate. If the results are still very different, then perhaps we need to average over more trials, i.e., replace the 100 with 200, or 500. :[font = text; inactive; preserveAspect; endGroup] In your homework, you will be asked to use the function "aveDraw" to answer the following two questions. If 10 random names are called each day, how many different people are likely to be called on? How many random names should be called so that 15 different people get called? :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] A Graphical Display :[font = text; inactive; preserveAspect] We might understand our problem better if we could see a graph of "draw[ ]" for different values of "n" or of "aveDraw[ ]" for different values of "n" and "trials". To do so, we need to give Mathematica a list of points to plot. The following "Table[ ]" command produces a list of pairs {i, draw[i]}, as "i" (our "x-coordinate") runs from one to five. :[font = input; preserveAspect] Table[ {i,draw[i]},{i,1,5}] :[font = text; inactive; preserveAspect] We can plot these pairs as xy-coordinates using "ListPlot[ ]" in the cell below. Recall that "%" denotes using the result of the last evaluation. (If the points are too small to see, click on the graphic, grab a corner, and drag it to a larger size.) :[font = input; preserveAspect] ListPlot[%] :[font = text; inactive; preserveAspect] The x-axis shows the number times the class was called on; the y-axis, the number of different people selected. Let's look at this graph as the number of times people are called on rises from one to one hundred. :[font = input; preserveAspect] ListPlot[ Table[ {i,draw[i]},{i,1,100}] ] :[font = text; inactive; preserveAspect] The y-values plotted here were the results of a single trial with "draw[i]". Let's look at the graph using "aveDraw[i,5]" for the y-value, i.e., using an average of five trials of "draw[i]" for each i. :[font = input; preserveAspect] ListPlot[ Table[ {i,aveDraw[i,5]},{i,1,100}] ] :[font = text; inactive; preserveAspect; endGroup; endGroup] In your homework you will be asked to use these functions to answer the original question in some detail. ^*)