Chapter II.  List-Based Programming

4. Introduction to Lists and Using Programming Principles

Last revision:  January 15 1998

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.

Mathematica operations/structures introduced: 
     Random
     Table
     Union
     Length
     Sum
     ListPlot

Problem Solving Strategies (Bottom-Up, Top-Down)

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 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?"

Bottom-Up Analysis

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.

Top-down Analysis

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 form there.  For extremely large problems top-down analysis can be useful in keeping the larger picture always in mind.

Example of Problem Solving: A Class Roster

Execute the following input cells.

numStuds = 15;
roster = 
{"Carr", "Crabtree", "Davis", "Dixon", "Herbert", "Jones", "Moore", "Moskowitz", "Naples", "Phillips", "Rice-Stitt", "Schenk", "Seifert", "Slaby", "Tarver"};

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?

Answer:  Without some mathematics, this problem is difficult to answer theoretically.  Empirically, however, we may simulate the situation and apply inductive reasoning.

Randomly Calling On One Student

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?

The Mathematica double-bracket notation allows us to select a particular element of the list.

roster[[5]]

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.

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" or look up Random in the Help browser if you are confused!)

Random[Integer,{1,numStuds}]

Putting the two together---using the result of the "Random[]" command inside the double-bracket notation---gives us a random name from the list.

roster[[  Random[Integer,{1,numStuds}]  ]]

Randomly Calling On Several Students

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.

Table[ r, {5} ]

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.

Table[ 
	 roster[[ Random[Integer,{1,numStuds}] ]], {5}
]

How about a list of fifteen random names?

Table[ 
  roster[[ Random[Integer,{1,numStuds}] ]], {15} 
]

Counting the Number of Distinct Students Called On

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:

Union[ {c,c,b,a,b,a,c,c,c} ]

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 random list of fifteen names.  To eliminate duplicates, we wrap "Union[]" around the command we're currently using to produce fifteen random names:

Union[
  Table[ 
    roster[[ Random[Integer,{1,numStuds}] ]], {15}
  ]
]

(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.

Length[ {3,3,5,5,6} ]

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:

Length[
  Union[
    Table[ 
      roster[[ Random[Integer,{1,numStuds}] ]], {15}
    ]
  ]
]

Writing a Function

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.

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:

Clear[square]
square[x_]:=x^2

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.

square[3]
square[{a,b,c}]

(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.

Clear[draw]
draw[n_]:=Length[
  Union[
    Table[ roster[[ Random[Integer,{1,numStuds}] ]],
      {n} 
    ]
  ]
]

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

draw[15]

This command reports how many different people fielded fifteen questions.  Similarly, if the class was called upon twenty-five times, we would execute

draw[25]

This command reports how many different people fielded 25 questions.

Approaching an Estimate

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.

Table[ draw[15], {10}]

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:

Sum[ r, {5}]

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.

Sum[ draw[40], {10} ] /10

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.

Clear[aveDraw]
aveDraw[n_,trials_] := 
	 N[ Sum[ draw[n], {trials} ] / trials ]

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.

aveDraw[15,100]

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.

aveDraw[15,100]

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.

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?

A Graphical Display

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.

Table[ {i,draw[i]},{i,1,5}]

Aside on FormatTypes:  Select the output cell above (for "Table[ {i,draw[i]},{i,1,5}]").  Then, under the Cell menu, look at the Convert to options.  Experiment with format types by selecting the options: InputForm, OutputForm, StandardForm, and TraditionalForm.  The latter displays this list of pairs as a rectangular array.

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.)

ListPlot[%]

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.

ListPlot[ Table[ {i,draw[i]},{i,1,100}]  ]

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.

ListPlot[ Table[ {i,aveDraw[i,5]},{i,1,100}]  ]

In your homework you will be asked to use these functions to answer the original question in some detail.