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.

Chapter II.  List-Based Programming

4. Introduction to Lists and Using Programming Principles

[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.]

Last revision:  September 5 1996

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.

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

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
from 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 =
{"Barrington", "Culbertson", "Edmundson", "Edwards",
"Harrington", "Henry", "Krause", "Lenhart", "Medendorp", "Mileham",
"Nelson", "Pfeiffer", "Sobczak", "Thomson", "Vogelbacher"};

[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.]

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" 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 rando
m 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}]

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.