View in EDS HTML Full Text PDF Full Text

Practical Programming Tasks for Better Understanding of Expectation in Computer Science Probability Courses

Saved in:
Bibliographic Details
Title: Practical Programming Tasks for Better Understanding of Expectation in Computer Science Probability Courses
Language: English
Authors: Nili Beck, Yelena Stukalin, Sigal Levy
Source: Teaching Statistics: An International Journal for Teachers. 2026 48(1):3-11.
Availability: Wiley. Available from: John Wiley & Sons, Inc. 111 River Street, Hoboken, NJ 07030. Tel: 800-835-6770; e-mail: cs-journals@wiley.com; Web site: https://www.wiley.com/en-us
Peer Reviewed: Y
Page Count: 9
Publication Date: 2026
Document Type: Journal Articles
Reports - Research
Descriptors: Programming, Expectation, Computer Science Education, Probability, Efficiency, Algorithms, Experiential Learning, Problem Solving, Difficulty Level, Task Analysis, Design
DOI: 10.1111/test.12402
ISSN: 0141-982X
1467-9639
Abstract: The concept of expectation is fundamental in computer science education, especially for analyzing the time efficiency of algorithms. However, the gap between theoretical knowledge and practical application can make it challenging for students to appreciate the importance of expectation in real-world contexts. This paper seeks to bridge that gap by highlighting the relationship between expectation and the population mean. To accomplish this, two experiments are presented, with tasks specifically designed to engage students in hands-on learning experiences in practical problem-solving. The first experiment focuses on the number of successes of the careless clerk, while the second experiment involves searching for all occurrences of a value in a randomly selected array, addressing the key question of the algorithm's expected time complexity. By presenting tasks that demonstrate the practical application of expectation, we aim to equip students with the tools needed to make informed decisions when designing and optimizing algorithms.
Abstractor: As Provided
Entry Date: 2026
Accession Number: EJ1494361
Database: ERIC
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
    Url: https://content.ebscohost.com/cds/retrieve?content=AQICAHj0k_4E0hTGH8RJwT4gCJyBsGNe_WN95AvKlDbXJGqwxwFTNGuVBg6_JHA5J4QHbpfPAAAA4zCB4AYJKoZIhvcNAQcGoIHSMIHPAgEAMIHJBgkqhkiG9w0BBwEwHgYJYIZIAWUDBAEuMBEEDKKVdaU0j4v9-2aVlgIBEICBmzDFF-ehoMKwT0sj4SCvoJ_waliu1yOLN1Lm8LK9nDqrVrR3dxUirIGFEHpE6VUm9cRp7BRonYgS5rhFGyNVscI6fu1X892c0ZwCZT_W9t37oeixsAozxWxsTUO3ez57lh6VOegsqwPG22J6suz4x57A1P6dQsy9oY4Pyb_umwnO6ziDP886e7_ifhdgK1Gq873RQi3jc7XaQ7xz
Text:
  Availability: 1
  Value: <anid>AN0190911868;d8y01mar.26;2026Jan19.06:04;v2.2.500</anid> <title id="AN0190911868-1">Practical programming tasks for better understanding of expectation in computer science probability courses </title> <p>The concept of expectation is fundamental in computer science education, especially for analyzing the time efficiency of algorithms. However, the gap between theoretical knowledge and practical application can make it challenging for students to appreciate the importance of expectation in real‐world contexts. This paper seeks to bridge that gap by highlighting the relationship between expectation and the population mean. To accomplish this, two experiments are presented, with tasks specifically designed to engage students in hands‐on learning experiences in practical problem‐solving. The first experiment focuses on the number of successes of the careless clerk, while the second experiment involves searching for all occurrences of a value in a randomly selected array, addressing the key question of the algorithm's expected time complexity. By presenting tasks that demonstrate the practical application of expectation, we aim to equip students with the tools needed to make informed decisions when designing and optimizing algorithms.</p> <p>Keywords: expectation; practical programming tasks; probability courses</p> <hd id="AN0190911868-2">INTRODUCTION</hd> <p>Recent research in probability education and computer science pedagogy has highlighted the need for innovative teaching methods that effectively bridge theoretical concepts with practical applications.[[<reflink idref="bib4" id="ref1">4</reflink>], [<reflink idref="bib6" id="ref2">6</reflink>]] Studies by Batanero and Álvarez‐Arroyo[<reflink idref="bib1" id="ref3">1</reflink>] have emphasized that traditional approaches, including simulation alone, may not suffice for fostering a deep understanding of complex probabilistic concepts. Meanwhile, Kazak and Pratt[<reflink idref="bib3" id="ref4">3</reflink>] have explored the potential of computational modeling in teaching probability, advocating for an integrated approach that connects data‐centric and theoretical perspectives. However, they also identified challenges in implementation, including the complexity of modeling for learners and the need for carefully designed pedagogical strategies. These findings underscore the importance of developing multifaceted teaching methods that combine theoretical foundations with hands‐on, computational experiences. Furthermore, past research has suggested that students benefit from culture‐oriented pedagogy. Embedding examples close to the students' culture or scientific field of interest may increase their motivation and result in a better understanding of the course material.[[<reflink idref="bib5" id="ref5">5</reflink>], [<reflink idref="bib7" id="ref6">7</reflink>]]</p> <p>This article explores an innovative approach to teaching probability and algorithm analysis in computer science education. We present two experiments and lesson outlines designed to deepen students' understanding of key concepts such as expectation, simulation, and algorithmic efficiency. By combining theoretical foundations with practical, hands‐on exercises, we aim to bridge the gap between abstract probabilistic concepts and their real‐world applications in computer science.</p> <p>A central focus of our approach is the concept of expectation, which is crucial in both probability theory and computer science. Expectation provides a powerful tool for analyzing average‐case behavior of algorithms and understanding probabilistic phenomena. To effectively convey this concept, we present two complementary methods for calculating expectation: one based on population averages and another using probability distributions. By demonstrating the equivalence of these methods through concrete examples, such as calculating the average age of a student population, we aim to help students develop an intuitive understanding of expectation that they can apply to more complex scenarios in algorithm analysis.</p> <p>These activities are intended for undergraduate computer science students who have already acquired some knowledge in programming and data structures and are able to implement simple programs in any language. The setting would be an introductory course in Probability theory, in which the topics of random variables, distributions, and expected values are introduced. Such activities can be delivered after the theoretical concepts have been studied and discussed, providing an additional perception of these concepts.</p> <p>We suggest a comprehensive lesson plan centered around the "careless clerk" problem. In this problem, we consider a clerk that assigns letters to envelopes randomly and counts the number of letters ("successes") that were assigned to their intended recipients. This lesson plan guides students through increasingly complex scenarios, starting with small‐scale manual calculations and progressing to large‐scale computer simulations. The plan is structured to help students grasp the relationship between individual outcomes and overall distributions, appreciate the power of computational methods in probability, and understand the concepts of sampling and estimation.</p> <p>Additionally, we propose two experiments: one focusing on simulating the careless clerk problem for various sample sizes and another on calculating the expected runtime in a search algorithm. These hands‐on activities are designed to reinforce theoretical concepts and provide students with practical experience in algorithm analysis and probabilistic thinking.</p> <p>Through these carefully crafted lessons and experiments, we aim to provide educators with effective tools to teach probability and algorithmic concepts in a way that is both engaging and deeply informative for computer science students.</p> <hd id="AN0190911868-3">ALGORITHM EFFICIENCY ANALYSIS</hd> <p>Examining algorithm efficiency is a fundamental aspect of theoretical computer science. It involves evaluating the computational resources required by an algorithm, particularly in terms of time complexity (usually measured by the order of magnitude of operations performed) and space complexity (the amount of memory utilized).</p> <p>Algorithm analysis is a well‐established field, extensively explored in numerous books and articles. See, for example.[[<reflink idref="bib8" id="ref7">8</reflink>]] The significance of algorithm analysis lies in its ability to determine whether a problem can be solved within reasonable time limits and to compare different solutions to find the most efficient one for a given problem.</p> <p>It is important to note that time complexity analysis is often asymptotic, focusing on how an algorithm behaves with large and complex inputs. Additionally, time complexity depends on the definition of a basic operation and the specific implementation of the algorithm, including the data structures it uses.</p> <hd id="AN0190911868-4">THE IMPORTANCE OF EXPECTATION FOR COMPUTER SCIENCE STUDENTS</hd> <p>It is important to analyze the expected time complexity of an algorithm, especially when a stochastic process influences the input's size, shape, or quality. On the other hand, some algorithms include random operations. In such cases, evaluating their time efficiency involves assessing the expected number of operations.</p> <p>Consider the quicksort algorithm, employed for sorting numbers. Quicksort[<reflink idref="bib2" id="ref8">2</reflink>] has various variations, yet its fundamental principle involves selecting a pivot element at each stage. Subsequently, the array values are partitioned into two subarrays: one containing elements no greater than the pivot and the other containing those greater than the pivot. These subarrays are then recursively sorted until their size is reduced below a predefined threshold, a specialized sorting technique can be utilized in this case. For example, sorting the numbers in the array (<reflink idref="bib4" id="ref9">4</reflink>, 2, 1, 7, 5, 3) could be done as follows:</p> <p></p> <ulist> <item> Randomly select a pivot – say 4 (arbitrarily, as it is the first number in this array)</item> <p></p> <item> Rearrange the array so that all numbers smaller than 4 are placed before it, and all numbers greater than 4 are placed after it. The result in this example would be: (<reflink idref="bib2" id="ref10">2</reflink>, 1, 3, 4, 7, 5).</item> <p></p> <item> Use the same procedure to sort the two subarrays (<reflink idref="bib2" id="ref11">2</reflink>, 1, 3) and (<reflink idref="bib7" id="ref12">7</reflink>, 5).</item> </ulist> <p>When a subarray contains only two elements, a straightforward comparison is sufficient to sort them.</p> <p>Because the selection of the pivot can involve randomness, analyzing the algorithm's time efficiency necessitates using probabilistic tools, particularly the ability to compute the expected number of performed operations.</p> <hd id="AN0190911868-5">TWO APPROACHES FOR CALCULATING THE EXPECTATION</hd> <p>There are two suitable methods for calculating the expectation. For instance, consider a population of 15 students, with 10 students aged 20 and 5 students aged 22. The average age of this population can be calculated as <ephtml> <math display="block" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0001" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac><mrow><mn>20</mn><mo>+</mo><mi>⋯</mi><mo>+</mo><mn>20</mn><mo>+</mo><mn>22</mn><mo>+</mo><mi>⋯</mi><mo>+</mo><mn>22</mn></mrow><mrow><mn>10</mn><mo>+</mo><mn>5</mn></mrow></mfrac><mo linebreak="goodbreak">=</mo><mfrac><mrow><mn>22</mn><mo>⋅</mo><mn>10</mn><mo>+</mo><mn>22</mn><mo>⋅</mo><mn>5</mn></mrow><mn>15</mn></mfrac><mo linebreak="goodbreak">=</mo><mn>20</mn><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow></math> </ephtml></p> <p>Another approach for this calculation is to view the age of a randomly chosen student as a random variable, which takes the value 20 with a probability of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0002" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac><mn>10</mn><mn>15</mn></mfrac></mrow></math> </ephtml> and the value 22 with a probability of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0003" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac><mn>5</mn><mn>15</mn></mfrac></mrow></math> </ephtml> . Following this perspective, the expectation can be computed as <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0004" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>20</mn><mo>⋅</mo><mfrac><mn>10</mn><mn>15</mn></mfrac><mo>+</mo><mn>22</mn><mo>⋅</mo><mfrac><mn>5</mn><mn>15</mn></mfrac><mo>=</mo><mn>20</mn><mfrac><mn>2</mn><mn>3</mn></mfrac></mrow></math> </ephtml> .</p> <p>These two methods are of course equivalent.</p> <p>These two approaches can also be employed to calculate the expected time efficiency of algorithms. Consider, for example, the quicksort algorithm discussed earlier. One method involves computing its efficiency by averaging the number of operations executed across all potential permutations of the numbers. Another approach entails randomly selecting a permutation of the numbers, calculating the number of performed operations, and calculating the average by repeating this experiment numerous times.</p> <p>While the difference between these two approaches is seemingly technical, it touches the very essence of the idea of expected value. Our aim is to use the practical tasks not to demonstrate the technical aspect of calculating expectation, but rather to evoke a deeper understanding among our students of what the expected value means and how it is derived. We believe that this understanding will provide a stronger foundation of key concepts in probability that are required in advanced computer science courses.</p> <p>We will demonstrate the implementation of these ideas on two experiments. The careless clerk problem is more probability‐oriented in its nature, while the algorithm for locating array entries is more related to computer science per se.</p> <hd id="AN0190911868-6">Experiment A—The number of successes of the careless clerk</hd> <p>In the careless clerk problem, a typist has written <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0005" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> letters and the corresponding <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0006" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> envelopes. A careless mailing clerk randomly placed the letters into the envelopes, one letter per envelope, without regard to their intended recipients. In this experiment, you will write a simulation which will evaluate the average number of letters that were correctly inserted into their respective envelopes. For this purpose, we will create a random permutation of the numbers <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0007" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>0</mn><mo>,</mo><mi>...</mi><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></math> </ephtml> and count the numbers that match their location. This will mark the number of successes of the careless clerk.</p> <p>Detailed lesson outline:</p> <p></p> <ulist> <item> Introduce the problem of the careless clerk: A clerk has a task of sending <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0008" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> letters. Specifically, they have a pile of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0009" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> letters all addressed to different people and a pile of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0010" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> envelopes with the recipients' addresses. Instead of matching the correct letter to each envelope, the careless clerk puts each letter in a randomly selected envelope. Let us consider the variable <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0011" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> – the number of letters that will reach the correct destination.</item> <p></p> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0012" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>3</mn></mrow></math> </ephtml> , perform the following:</item> <p></p> <item> List all possible permutations.</item> <p></p> <item> Calculate the mean across all permutations, considering each possible permutation as a single observation.</item> <p></p> <item> Calculate the distribution of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0013" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> and find its expectation.</item> <p></p> <item> Take a random sample of 1,000,000 observations from the distribution you found in (iii) and calculate the sample mean.</item> <p></p> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0014" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>10</mn></mrow></math> </ephtml> , perform the following:</item> <p></p> <item> It is not feasible to list all possible <emph>10!</emph> permutations. Therefore, use a simulation to do that: write a code that calculates the value of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0015" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> for each possible permutation.</item> <p></p> <item> Follow steps a.ii‐a.</item> <p></p> </ulist> <p>• above.</p> <p></p> <ulist> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0016" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>100</mn></mrow></math> </ephtml> , perform the following:</item> <p></p> <item> It is not feasible to list all permutations,</item> <p></p> <item> Nor is it feasible for a computer simulation to cover all permutations – it requires incredible computational resources.</item> <p></p> <item> Therefore, select a <emph>random sample</emph> of 1,000,000 permutations and calculate the mean across all permutations.</item> </ulist> <p>This outline aims at the following:</p> <p>For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0017" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>3</mn></mrow></math> </ephtml> , the students learn that the <emph>expectation</emph> is equivalent to a sample mean taken across all possible population items. They can visualize the population and perform calculations on both the individual items and the distribution. They also learn that the expectation is the mean value of an infinite (or very large, for practical purposes) number of observations taken from a given distribution.</p> <p>The task given to the students will read:</p> <p>Let <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0018" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> be the number of letters that will reach the correct destination after being randomly assigned by the careless clerk.</p> <p></p> <ulist> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0019" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>3</mn></mrow></math> </ephtml> , perform the following:</item> <p></p> <item> List all possible permutations.</item> <p></p> <item> Calculate the mean across all permutations, considering each possible permutation as a single observation.</item> <p></p> <item> Calculate the distribution of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0020" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> and find its expectation.</item> <p></p> <item> Take a random sample of 1,000,000 observations from the distribution you found in (iii) and calculate the sample mean.</item> <p></p> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0021" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>10</mn></mrow></math> </ephtml> , perform the following:</item> <p></p> <item> Write a code that calculates the value of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0022" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> for each possible permutation.</item> <p></p> <item> Follow steps a.ii‐a.</item> <p></p> </ulist> <p>• above.</p> <p></p> <ulist> <item> For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0023" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>100</mn></mrow></math> </ephtml> , select a random sample of 1,000,000 permutations and calculate the mean across all permutations.</item> </ulist> <p>The resulting answers are:</p> <p>For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0024" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>3</mn></mrow></math> </ephtml></p> <p></p> <ulist> <item> Let A, B, C denote the addresses on the envelopes, and let a, b, c denote the respective letters. The possible permutations, and the resulting values of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0025" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> , are presented in Table 1.</item> </ulist> <p>1 TABLE Permutations and number of correct assignments.</p> <p> <ephtml> <table><thead valign="bottom"><tr><th align="left">A</th><th align="left">B</th><th align="left">C</th><th align="left"><p><math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0026" xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mi>X</mi></mrow></math></p></th></tr></thead><tbody valign="top"><tr><td align="left">a</td><td align="left">b</td><td align="left">c</td><td align="left">3</td></tr><tr><td align="left">a</td><td align="left">c</td><td align="left">b</td><td align="left">1</td></tr><tr><td align="left">b</td><td align="left">a</td><td align="left">c</td><td align="left">1</td></tr><tr><td align="left">b</td><td align="left">c</td><td align="left">a</td><td align="left">0</td></tr><tr><td align="left">c</td><td align="left">a</td><td align="left">b</td><td align="left">0</td></tr><tr><td align="left">c</td><td align="left">b</td><td align="left">a</td><td align="left">1</td></tr></tbody></table> </ephtml> </p> <p> <ephtml> <math display="block" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0027" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mover accent="true"><mi>X</mi><mo>¯</mo></mover><mo linebreak="goodbreak">=</mo><mi>E</mi><mfenced open="(" close=")"><mi>X</mi></mfenced><mo linebreak="goodbreak">=</mo><mfrac><mrow><mn>3</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>1</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>0</mn><mo>+</mo><mn>1</mn></mrow><mn>6</mn></mfrac><mo linebreak="goodbreak">=</mo><mn>1</mn></mrow></math> </ephtml> </p> <p></p> <ulist> <item> The distribution of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0028" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> is given in Table 2 , followed by the resulting expectation.</item> <item>he theoretical distribution of the number of correctly placed letters.</item> </ulist> <p> <ephtml> <table><thead valign="bottom"><tr><th align="left"><p><math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0029" xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mi>X</mi></mrow></math></p></th><th align="left">0</th><th align="left">1</th><th align="left">3</th></tr></thead><tbody valign="top"><tr><td align="left">P(x)</td><td align="left">2/6</td><td align="left">3/6</td><td align="left">1/6</td></tr></tbody></table> </ephtml> </p> <p> <ephtml> <math display="block" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0030" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>E</mi><mfenced open="(" close=")"><mi>X</mi></mfenced><mo linebreak="goodbreak">=</mo><mn>0</mn><mo>⋅</mo><mfrac><mn>2</mn><mn>6</mn></mfrac><mo linebreak="goodbreak">+</mo><mn>1</mn><mo>⋅</mo><mfrac><mn>3</mn><mn>6</mn></mfrac><mo linebreak="goodbreak">+</mo><mn>3</mn><mo>⋅</mo><mfrac><mn>1</mn><mn>6</mn></mfrac><mo linebreak="goodbreak">=</mo><mn>1</mn></mrow></math> </ephtml> </p> <p></p> <ulist> <item> This answer will vary between students as it is based on a random sample. We expect a result that is close to 1. In our example, the mean value of the observations was 1.001146.</item> </ulist> <p>For <emph>n</emph> = 10, the students have the same observation on a much larger population and learn to appreciate the power of a simulation in calculating population parameters. We will not present the entire set of permutations with the respective values of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0031" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> . However, we can show the distribution of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0032" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> as obtained by the simulation, as presented in Table 3.</p> <p>3 TABLE The empirical distribution of the number of correctly placed letters in Experiment A(b).</p> <p> <ephtml> <table><thead valign="bottom"><tr><th align="left"><p><math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0033" xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mi>X</mi></mrow></math></p></th><th align="left"><italic>f</italic>(<italic>x</italic>)</th><th align="left"><italic>P</italic>(<italic>x</italic>) <italic>= f</italic>(<italic>x</italic>)/10!</th></tr></thead><tbody valign="top"><tr><td align="left">0</td><td align="char" char=".">1,334,961</td><td align="char" char=".">0.368</td></tr><tr><td align="left">1</td><td align="char" char=".">1,334,960</td><td align="char" char=".">0.368</td></tr><tr><td align="left">2</td><td align="char" char=".">667,685</td><td align="char" char=".">0.184</td></tr><tr><td align="left">3</td><td align="char" char=".">222,480</td><td align="char" char=".">0.0613</td></tr><tr><td align="left">4</td><td align="char" char=".">55,650</td><td align="char" char=".">0.0153</td></tr><tr><td align="left">5</td><td align="char" char=".">11,088</td><td align="char" char=".">0.00306</td></tr><tr><td align="left">6</td><td align="char" char=".">1890</td><td align="char" char=".">5.21e‐4</td></tr><tr><td align="left">7</td><td align="char" char=".">240</td><td align="char" char=".">6.61e‐5</td></tr><tr><td align="left">8</td><td align="char" char=".">45</td><td align="char" char=".">1.24e‐5</td></tr><tr><td align="left">10</td><td align="char" char=".">1</td><td align="char" char=".">2.76e‐7</td></tr></tbody></table> </ephtml> </p> <p> <ephtml> <math display="block" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0034" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>E</mi><mfenced open="(" close=")"><mi>X</mi></mfenced><mo linebreak="goodbreak">=</mo><mn>0</mn><mo>⋅</mo><mn>0.368</mn><mo linebreak="goodbreak">+</mo><mn>1</mn><mo>⋅</mo><mn>0.368</mn><mo linebreak="goodbreak">+</mo><mn>2</mn><mo>⋅</mo><mn>0.184</mn><mo linebreak="goodbreak">+</mo><mi>⋯</mi><mo linebreak="goodbreak">+</mo><mn>10</mn><mo>⋅</mo><mn>2.76</mn><msup><mi>e</mi><mrow><mo>−</mo><mn>7</mn></mrow></msup><mo linebreak="goodbreak">=</mo><mn>1</mn></mrow></math> </ephtml> </p> <p>For <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0035" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>100</mn></mrow></math> </ephtml> , the students are introduced to the concepts of a sample and an estimator. In this simulation, we randomly selected a sample of 1,000,000 permutations with replacement. The estimated probabilities of the three lowest values of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0036" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi></mrow></math> </ephtml> are presented in Table 4.</p> <p>4 TABLE The partial empirical distribution of the number of correctly placed letters in Experiment A(c).</p> <p> <ephtml> <table><thead valign="bottom"><tr><th align="left"><italic>x</italic></th><th align="left"><italic>f</italic>(<italic>x</italic>)</th><th align="left"><italic>f</italic>(<italic>x</italic>)/100,000</th></tr></thead><tbody valign="top"><tr><td align="left">0</td><td align="left">36,764</td><td align="left">0.368</td></tr><tr><td align="left">1</td><td align="left">36,807</td><td align="left">0.368</td></tr><tr><td align="left">2</td><td align="left">18,367</td><td align="left">0.184</td></tr><tr><td align="left">...</td><td align="left">...</td><td align="left">...</td></tr><tr><td align="left">...</td><td align="left">...</td><td align="left">...</td></tr><tr><td align="left">100</td><td align="left">0</td><td align="left">0</td></tr></tbody></table> </ephtml> </p> <p>As before, this answer will vary between students as it is based on a random sample. In this calculation, we obtained an estimated expectation of 1.000687.</p> <hd id="AN0190911868-7">Experiment B: Locating array entries—mean runtime analysis</hd> <p>Consider the following problem: <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0037" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> high‐tech company employees are asked to select one gift each as their New Year's bonus. There are <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0038" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> gifts to choose from. Given a specific gift, your task is to create a list of all employees who chose that gift.</p> <p>Detailed lesson outline:</p> <p>The programming implementation of this problem is the following: let us number the employees <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0039" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>,</mo><mi>...</mi><mo>,</mo><mi>n</mi></mrow></math> </ephtml> , and the gifts <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0040" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>,</mo><mi>...</mi><mo>,</mo><mi>k</mi></mrow></math> </ephtml> . The choices are stored in an array indexed 1 through <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0041" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> , where each entry is a number between 1 and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0042" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> , representing the gift selected by the respective employee. Therefore, the list of employees who chose gift <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0043" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> is a list of all array indices for which the entry is <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0044" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> .</p> <p></p> <ulist> <item> Generate an array of the employees' selections and select a gift for which a list should be created.</item> <p></p> <item> Create a list of indices containing the selected gift while counting the number of actions the algorithm has performed.</item> </ulist> <p>In its central part, this algorithm consists of two primary actions: comparison, which is done precisely <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0045" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> times and requires no further analysis, and adding a number to a list, which will be done as many times as the number <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0046" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> was drawn to the array. As adding an entry to the list may be a computationally resource‐consuming action, estimating the algorithm's runtime by the number of additions it performs is reasonable.</p> <p>The complexity of this algorithm derives from the random selection of the array assignments. Since all values between 1 and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0047" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> are drawn with equal probability, the number of cells containing the value <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0048" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> follows a binomial distribution: <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0049" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>~</mo><mi mathvariant="italic">Bin</mi><mfenced open="(" close=")" separators=","><mi>n</mi><mfrac bevelled="true"><mn>1</mn><mi>k</mi></mfrac></mfenced></mrow></math> </ephtml> . The expected number of cells containing the value <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0050" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> , equivalent to the number of additions to the list, is <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0051" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>E</mi><mfenced open="(" close=")"><mi>X</mi></mfenced><mo>=</mo><mfrac bevelled="true"><mi>n</mi><mi>k</mi></mfrac></mrow></math> </ephtml> . The students will be asked to test the mean runtime for different values of n and k.</p> <p></p> <ulist> <item> Calculate the runtime for several instances of the problem, varying in <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0052" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0053" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> . Plot the runtime against <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0054" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> , <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0055" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0056" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac bevelled="true"><mi>n</mi><mi>k</mi></mfrac></mrow></math> </ephtml> .</item> </ulist> <p>This outline aims at the following: By performing this task, the students learn that while an algorithm's actual runtime is random and may vary between different instances even under similar parameters, the mean runtime follows a pattern that can be analyzed using probabilistic and statistical tools. We expect to see that the runtime is a linear function of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0057" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0058" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac bevelled="true"><mi>n</mi><mi>k</mi></mfrac></mrow></math> </ephtml> , and an inverse function of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0059" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> .</p> <p>The task given to the students will read:</p> <p>(a) Simulate the problem (assuming equal probability for selecting all gifts)</p> <p> <emph>Step 1: Simulate the employees' selections</emph> </p> <p></p> <ulist> <item> Initialize an array A of size <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0060" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> .</item> <p></p> <item> For each cell in this array, assign a randomly selected number in the range <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0061" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced open="[" close="]" separators=",,"><mn>1</mn><mi>...</mi><mi>k</mi></mfenced></mrow></math> </ephtml> .</item> </ulist> <p> <emph>Step 2: Select the gift for which a list should be created</emph> </p> <p></p> <ulist> <item> Randomly select a number <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0062" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> between 1 and <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0063" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> .</item> </ulist> <p> <emph>Step 3: Search and create the list of indices containing gift</emph> <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0064" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi></mrow></math> </ephtml> </p> <p></p> <ulist> <item> Initialize a list.</item> <p></p> <item> For each cell <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0065" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced open="[" close="]"><mi>i</mi></mfenced></mrow></math> </ephtml> ( <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0066" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>...</mi><mo>,</mo><mi>n</mi></mrow></math> </ephtml> ) of the array, if <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0067" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>A</mi><mfenced open="[" close="]"><mi>i</mi></mfenced><mo>=</mo><mo>=</mo><mi>j</mi></mrow></math> </ephtml> , then add <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0068" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi></mrow></math> </ephtml> to the list.</item> <p></p> <item> Return the list.</item> </ulist> <p>(b) The counter</p> <p></p> <ulist> <item> Set a counter to 0.</item> <p></p> <item> Amend stages 5–6 so that every addition to the list increases the counter by 1. Return the counter's value to estimate runtime.</item> </ulist> <p>(c) Calculating the runtime for different instances of this problem</p> <p></p> <ulist> <item> Set <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0069" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>10</mn></mrow></math> </ephtml> and run this algorithm 100 times for each value of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0070" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>=</mo><mn>10</mn><mo>,</mo><mn>15</mn><mo>,</mo><mn>20</mn><mo>,</mo><mn>25</mn><mo>,</mo><mn>30</mn></mrow></math> </ephtml> . Calculate the mean runtime in each case and its standard deviation.</item> <p></p> <item> Plot a graph of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0071" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> against the mean runtime.</item> <p></p> <item> Repeat stages 9–10 for <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0072" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>5</mn><mo>,</mo><mn>20</mn><mo>,</mo><mn>25</mn><mo>,</mo><mn>30</mn></mrow></math> </ephtml> . What function do the graphs show?</item> <p></p> <item> Use the previous results to plot, for each <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0073" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> , a graph of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0074" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> against the mean runtime. What function do the graphs show?</item> <p></p> <item> Finally, plot the runtime against <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0075" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac bevelled="true"><mi>n</mi><mi>k</mi></mfrac></mrow></math> </ephtml> using all combinations. What function does the graph show?</item> <p></p> <item> Use the binomial distribution to mathematically analyze this algorithm's runtime. Compare the results to the simulated graphs.</item> <p></p> <item> Is the runtime constant for each combination of parameters? Explain your answer.</item> </ulist> <p>Some sample graphs are shown in Figures 1–4. Looking at the graphs, we see that the order of the runtime is a linear function of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0076" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi></mrow></math> </ephtml> and an inverse function of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0077" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi></mrow></math> </ephtml> (linear function of <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0078" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac bevelled="true"><mn>1</mn><mi>k</mi></mfrac></mrow></math> </ephtml> ). This is supported by the mathematical analysis that shows that runtime's order follows a binomial distribution, and so the expected runtime's order is <ephtml> <math display="inline" overflow="scroll" altimg="urn:x-wiley:0141982X:media:test12402:test12402-math-0079" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfrac bevelled="true"><mi>n</mi><mi>k</mi></mfrac></mrow></math> </ephtml> . The students can visually see how the order of the runtime relates to the algorithm's parameters.</p> <p> <img src="https://imageserver.ebscohost.com/img/embimages/rdk/D8Y/01mar26/test12402-fig-0001.jpg?ephost1=dGJyMNXb4kSepq84yOvqOLCmsE6epq5Srqa4SK6WxWXS" alt="test12402-fig-0001.jpg" title="1 Runtime as a function of n for k=10." /> </p> <p></p> <p> <img src="https://imageserver.ebscohost.com/img/embimages/rdk/D8Y/01mar26/test12402-fig-0002.jpg?ephost1=dGJyMNXb4kSepq84yOvqOLCmsE6epq5Srqa4SK6WxWXS" alt="test12402-fig-0002.jpg" title="2 Runtime as a function of n for k=20." /> </p> <p></p> <p> <img src="https://imageserver.ebscohost.com/img/embimages/rdk/D8Y/01mar26/test12402-fig-0003.jpg?ephost1=dGJyMNXb4kSepq84yOvqOLCmsE6epq5Srqa4SK6WxWXS" alt="test12402-fig-0003.jpg" title="3 Runtime as a function of k for n = 10." /> </p> <p></p> <p> <img src="https://imageserver.ebscohost.com/img/embimages/rdk/D8Y/01mar26/test12402-fig-0004.jpg?ephost1=dGJyMNXb4kSepq84yOvqOLCmsE6epq5Srqa4SK6WxWXS" alt="test12402-fig-0004.jpg" title="4 Runtime as a function of k for n=20." /> </p> <p></p> <hd id="AN0190911868-12">CONCLUSION</hd> <p>This research focuses on illustrating the critical concept of expectation in statistics using ideas that students are already familiar with. The teaching approach targets students with some programming experience and a basic understanding of software engineering and algorithm analysis, enrolled in an introductory probability course.</p> <p>In this paper, we focused on two key connections related to the concept of expectation: one between expectation and the population mean and another between the concept of expectation in probability and the expected running time, a crucial concept in algorithm efficiency analysis. We also suggest that the efficiency of these tasks be tested by short quizzes that follow. An example question for such a quiz may be the following:</p> <p>A large retail company uses two software programs for entering data on new purchases. Program A has a mean processing time of 10 s per purchase, while Program B has a mean processing time of 20 s per purchase. In the following questions, assume that "a very large number" effectively represents an infinite number of repetitions of the process.</p> <p>For each statement below, select the best answer.</p> <p></p> <ulist> <item> Both programs are run to enter data for a single new purchase. The entry in Program A will certainly be faster than the entry in Program B.</item> <p></p> </ulist> <p>• True</p> <p></p> <p>• False</p> <p>Correct answer: False. The students are expected to understand that a single observation does not necessarily represent the mean of a large number of observations.</p> <p></p> <ulist> <item> Both programs are used to enter data for a very large number of new purchases (with the same purchases entered in each). The average time required to enter data in Program A will likely be about half of the average time in Program B.</item> <p></p> </ulist> <p>• True</p> <p></p> <p>• False</p> <p>Correct answer: True. The students are expected to understand that the mean of a very large number of observations should converge to the expected runtime value.</p> <p></p> <ulist> <item> Program A is used to enter data for 100 new purchases and then for 100,000 new purchases. Which of the following statements is correct? (Select one)</item> <p></p> <item> The average time required for entering 100,000 new purchases is larger than that required to enter 100 new purchases.</item> <p></p> <item> The average time required for entering 100,000 purchases should be closer to 10 seconds than that required to enter 100 purchases.</item> <p></p> <item> The proportion of purchases that will take exactly 10 seconds to enter is larger when entering 100,000 purchases than when entering 100 purchases.</item> </ulist> <p>Correct answer: ii. The students are expected to understand that for larger samples, the sample mean is a better representation of the true expected value.</p> <p>We advocate for advancing and modernizing the teaching of statistics by leveraging current technology and tools accessible to students. We are eager to continue developing this approach to elucidate additional concepts such as variance, correlation coefficient, the law of large numbers, the central limit theorem, and foundational ideas in estimation.</p> <p>It should be noted that students from disciplines other than computer science may benefit from similar activities using platforms that do not require the knowledge of any specific programming language.</p> <hd id="AN0190911868-13">A APPENDIX</hd> <p>Psuedo code</p> <p>Experiment A – The careless clerk problem</p> <p>For n=3</p> <p>howmany = 1000000</p> <p>for i=1,..., howmany</p> <p>x = a sample from the distribution</p> <p></p> <p> <ephtml> <table><tbody valign="top"><tr><td align="left"><p>Value</p></td><td align="left"><p>0</p></td><td align="left"><p>1</p></td><td align="left"><p>3</p></td></tr><tr><td align="left"><p>Probablity</p></td><td align="left"><p>2/6</p></td><td align="left"><p>3/6</p></td><td align="left"><p>1/6</p></td></tr></tbody></table> </ephtml> </p> <p>sumX = sumX + x</p> <p>print ("the average is", sumX/howmany)</p> <p>For n=10</p> <p>permutations = a list of all possible permutations on 1,..., n</p> <p>totalcount = 0</p> <p>zero all values in an array dist of size n+1</p> <p>for perm in permutations:</p> <p>count = the number of places in perm for which prem[i] = i</p> <p>increament tha value in dist[count] by 1</p> <p>totalcount += count</p> <p>print("the average is:", totalcount/n!)</p> <p>Exp = 0</p> <p>for i = 0, n</p> <p>Exp += (i*dist[i]/n!)</p> <p>print("The expectation is", Exp)</p> <p>For n=100</p> <p>howmany = 1000000</p> <p>totalCount = 0</p> <p>for i=1,..., howmany</p> <p>perm = a random permutation on the values 1,..., n</p> <p>count = the number of places in perm for which prem[i] = i</p> <p>totalcount += count</p> <p>print("The average is", totalCount /howmany)</p> <p>Experiment B –Locating array entries</p> <p>howmany = 1000</p> <p>for k in [<reflink idref="bib5" id="ref13">5</reflink>,<reflink idref="bib20" id="ref14">20</reflink>,<reflink idref="bib25" id="ref15">25</reflink>,<reflink idref="bib30" id="ref16">30</reflink>]</p> <p>for n in [<reflink idref="bib10" id="ref17">10</reflink>,<reflink idref="bib50" id="ref18">50</reflink>,<reflink idref="bib100" id="ref19">100</reflink>,<reflink idref="bib300" id="ref20">300</reflink>,<reflink idref="bib500" id="ref21">500</reflink>]</p> <p>sumcount= 0</p> <p>for h in 1,..., howmany</p> <p>arr = a random array of size n with values uniformly selected in 1,..., k</p> <p>j = a random value uniformly selected in 1,..., k</p> <p>count = 0</p> <p>for i in 1,...., n</p> <p> if (arr[i] == j) count = count +1</p> <p>sumcount = sumcount + count</p> <p>print("and the average is", sumcount/howmany)</p> <p>Simulation</p> <p>The simulation code for both experiments is provided below. We choose to develop the code in Python.</p> <p>def countSame(n, perm):</p> <p>"""The function counts how many points in perm satisfy perm[i]=i"""</p> <p>count = 0</p> <p>for i in range(n):</p> <p>if (perm[i] == i):</p> <p>count = count + 1</p> <p>return(count)</p> <p># This code implements Experiment A (a)</p> <p># For n=3, it takes a random sample of 1,000,000 observations from the careless clerk distribution.</p> <p># and calculates the sample mean.</p> <p>from numpy import random</p> <p>from numpy import sum</p> <p>howmany = 1000000</p> <p>x = random. choice([0, 1, 3], p=[2/6, 3/6, 1/6], size=(howmany))</p> <p>sumX = sum(x)</p> <p>print(sumX/howmany)</p> <p># This code implements Experiment A (b)</p> <p># For n=10, it calculates the average number of letters that reach their correct destination in the careless clerk problem,</p> <p># across all possible permutations.</p> <p>import itertools</p> <p>from math import factorial</p> <p>n = 10</p> <p>dist = [0 * i for i in range(n+1)]</p> <p>numbers = list(range(n))</p> <p>permutations = list(itertools.permutations(numbers))</p> <p>totalcount = 0</p> <p>for perm in permutations:</p> <p>count = countSame(n,perm)</p> <p>dist[count] += 1</p> <p>totalcount += count</p> <p>print("The average is", totalcount/factorial(n))</p> <p>print("The distribution is")</p> <p>Exp = 0</p> <p>for i in range(0, n+1):</p> <p>print ("%3d %7d %1.7f" % (i, dist[i], dist[i]/factorial(n)))</p> <p>Exp += (i*dist[i]/factorial(n))</p> <p>print()</p> <p>print("The expectation is", Exp)</p> <p># This code implements Experiment A (c)</p> <p># For n=100, this code generates 1,000,000 randomly selected permutations of size n</p> <p># and calculates the distribution and average number of letters that reach their correct destination</p> <p># in the careless clerk problem.</p> <p>import numpy</p> <p>from math import factorial</p> <p>numpy.random.seed()</p> <p>howmany = 1000000</p> <p>totalCount = 0</p> <p>n=100</p> <p>dist = [0 * i for i in range(n+1)]</p> <p>for i in range(howmany):</p> <p>perm = numpy.random.permutation(n)</p> <p>count = countSame(n, perm)</p> <p>dist[count] += 1</p> <p>totalCount += count</p> <p>print("The average is", totalCount /howmany)</p> <p>print("dist[0] =", dist[0])</p> <p>print("dist[<reflink idref="bib1" id="ref22">1</reflink>] =", dist[<reflink idref="bib1" id="ref23">1</reflink>])</p> <p>print("dist[<reflink idref="bib2" id="ref24">2</reflink>] =", dist[<reflink idref="bib2" id="ref25">2</reflink>])</p> <p>print("dist[<reflink idref="bib100" id="ref26">100</reflink>] =", dist[<reflink idref="bib100" id="ref27">100</reflink>])</p> <p># This code implements Experiment B</p> <p># For different values of n and k, it randomly initializes an array of size n with values in the range 1..k</p> <p># It then randomly selects an additional number within this range and counts how many times it appears in the array.</p> <p>import numpy</p> <p>import matplotlib.pyplot as plt</p> <p>numpy.random.seed()</p> <p>howmany = 1000</p> <p>listofn = [<reflink idref="bib10" id="ref28">10</reflink>,<reflink idref="bib50" id="ref29">50</reflink>,<reflink idref="bib100" id="ref30">100</reflink>,<reflink idref="bib300" id="ref31">300</reflink>,<reflink idref="bib500" id="ref32">500</reflink>]</p> <p>listofk = [<reflink idref="bib5" id="ref33">5</reflink>,<reflink idref="bib20" id="ref34">20</reflink>,<reflink idref="bib25" id="ref35">25</reflink>,<reflink idref="bib30" id="ref36">30</reflink>]</p> <p>for k in listofk:</p> <p>for n in listofn:</p> <p>print("n=", n, "k=", k, "first 5 results", end =" ")</p> <p>sumcount= 0</p> <p>for h in range(howmany):</p> <p>arr = numpy.random.randint(<reflink idref="bib1" id="ref37">1</reflink>, high=k+1, size=n)</p> <p>j = numpy.random.randint(<reflink idref="bib1" id="ref38">1</reflink>, high = k+1)</p> <p>count = 0</p> <p>for i in range(n):</p> <p>if (arr[i] == j):</p> <p> count += 1</p> <p>if (h < 5):</p> <p>print(count, end =" ")</p> <p>sumcount += count</p> <p>print("and the average is", sumcount/howmany)</p> <ref id="AN0190911868-14"> <title> REFERENCES </title> <blist> <bibl id="bib1" idref="ref3" type="bt">1</bibl> <bibtext> C. Batanero and R. Álvarez‐Arroyo, Teaching and learning of probability, ZDM 56 (2024), no. 1, 5 – 17. https://doi.org/10.1007/s11858-023-01511-5.</bibtext> </blist> <blist> <bibl id="bib2" idref="ref8" type="bt">2</bibl> <bibtext> C. A. R. Hoare, Quicksort, Comput. J. 5 (1962), no. 1, 10 – 16. https://doi.org/10.1093/comjnl/5.1.10.</bibtext> </blist> <blist> <bibl id="bib3" idref="ref4" type="bt">3</bibl> <bibtext> S. Kazak and D. Pratt, Developing the role of modelling in the teaching and learning of probability, Res. Math. Educ. 23 (2021), 113 – 133. https://doi.org/10.1080/14794802.2020.1802328.</bibtext> </blist> <blist> <bibl id="bib4" idref="ref1" type="bt">4</bibl> <bibtext> C. Langrall, K. Makar, P. Nilsson, and J. M. Shaughnessy, " Teaching and learning probability and statistics: An integrated perspective ," Compendium for research in mathematics education, J. Cai (ed.), The National Council of Teachers of Mathematics, Inc., Reston, VA, 2017, pp. 267 – 291.</bibtext> </blist> <blist> <bibl id="bib5" idref="ref5" type="bt">5</bibl> <bibtext> L. Lesser, A. Wagler, and B. Salazar, Flipping between languages? An exploratory analysis of the usage by Spanish‐speaking English language learner tertiary students of a bilingual probability applet, Stat. Educ. Res. J. 15 (2016), no. 2, 145 – 168. https://iase‐web.org/documents/SERJ/SERJ15(2)_Lesser.pdf.</bibtext> </blist> <blist> <bibl id="bib6" idref="ref2" type="bt">6</bibl> <bibtext> S. Levy, Y. Stukalin, and N. Guttmann‐Beck, Using practical programming tasks to enhance combinatorial understanding, Teach. Stat. 46 (2024), 113 – 120. https://doi.org/10.1111/test.12369.</bibtext> </blist> <blist> <bibl id="bib7" idref="ref6" type="bt">7</bibl> <bibtext> S. Levy and Y. Stukalin, " Introducing statistics to ultra‐Orthodox Jewish students by examples from the Bible ," Bridging the gap: Empowering & Educating Today's learners in statistics. Proceedings of the 11th international conference on teaching statistics (ICOTS11 2022), S. A. Peters, L. Zapata‐Cardona, F. Bonafini, and A. Fan (eds.), International Association for Statistical Education, Rosario, Argentina, 2022. https://iase-web.org/icots/11/proceedings/pdfs/ICOTS11_279_LEVY.pdf.</bibtext> </blist> <blist> <bibl id="bib8" idref="ref7" type="bt">8</bibl> <bibtext> C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: Algorithms and complexity, Dover Publications, New York, 1998.</bibtext> </blist> <blist> <bibl id="bib9" type="bt">9</bibl> <bibtext> C. H. Papadimitriou, Computational complexity, Addison‐Wesley, Reading, MA, 1994.</bibtext> </blist> </ref> <aug> <p>By Nili Beck; Yelena Stukalin and Sigal Levy</p> <p>Reported by Author; Author; Author</p> </aug> <nolink nlid="nl1" bibid="bib20" firstref="ref14"></nolink> <nolink nlid="nl2" bibid="bib25" firstref="ref15"></nolink> <nolink nlid="nl3" bibid="bib30" firstref="ref16"></nolink> <nolink nlid="nl4" bibid="bib10" firstref="ref17"></nolink> <nolink nlid="nl5" bibid="bib50" firstref="ref18"></nolink> <nolink nlid="nl6" bibid="bib100" firstref="ref19"></nolink> <nolink nlid="nl7" bibid="bib300" firstref="ref20"></nolink> <nolink nlid="nl8" bibid="bib500" firstref="ref21"></nolink>
Header DbId: eric
DbLabel: ERIC
An: EJ1494361
AccessLevel: 3
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Practical Programming Tasks for Better Understanding of Expectation in Computer Science Probability Courses
– Name: Language
  Label: Language
  Group: Lang
  Data: English
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Nili+Beck%22">Nili Beck</searchLink><br /><searchLink fieldCode="AR" term="%22Yelena+Stukalin%22">Yelena Stukalin</searchLink><br /><searchLink fieldCode="AR" term="%22Sigal+Levy%22">Sigal Levy</searchLink>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="SO" term="%22Teaching+Statistics%3A+An+International+Journal+for+Teachers%22"><i>Teaching Statistics: An International Journal for Teachers</i></searchLink>. 2026 48(1):3-11.
– Name: Avail
  Label: Availability
  Group: Avail
  Data: Wiley. Available from: John Wiley & Sons, Inc. 111 River Street, Hoboken, NJ 07030. Tel: 800-835-6770; e-mail: cs-journals@wiley.com; Web site: https://www.wiley.com/en-us
– Name: PeerReviewed
  Label: Peer Reviewed
  Group: SrcInfo
  Data: Y
– Name: Pages
  Label: Page Count
  Group: Src
  Data: 9
– Name: DatePubCY
  Label: Publication Date
  Group: Date
  Data: 2026
– Name: TypeDocument
  Label: Document Type
  Group: TypDoc
  Data: Journal Articles<br />Reports - Research
– Name: Subject
  Label: Descriptors
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Programming%22">Programming</searchLink><br /><searchLink fieldCode="DE" term="%22Expectation%22">Expectation</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+Science+Education%22">Computer Science Education</searchLink><br /><searchLink fieldCode="DE" term="%22Probability%22">Probability</searchLink><br /><searchLink fieldCode="DE" term="%22Efficiency%22">Efficiency</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Experiential+Learning%22">Experiential Learning</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+Solving%22">Problem Solving</searchLink><br /><searchLink fieldCode="DE" term="%22Difficulty+Level%22">Difficulty Level</searchLink><br /><searchLink fieldCode="DE" term="%22Task+Analysis%22">Task Analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Design%22">Design</searchLink>
– Name: DOI
  Label: DOI
  Group: ID
  Data: 10.1111/test.12402
– Name: ISSN
  Label: ISSN
  Group: ISSN
  Data: 0141-982X<br />1467-9639
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The concept of expectation is fundamental in computer science education, especially for analyzing the time efficiency of algorithms. However, the gap between theoretical knowledge and practical application can make it challenging for students to appreciate the importance of expectation in real-world contexts. This paper seeks to bridge that gap by highlighting the relationship between expectation and the population mean. To accomplish this, two experiments are presented, with tasks specifically designed to engage students in hands-on learning experiences in practical problem-solving. The first experiment focuses on the number of successes of the careless clerk, while the second experiment involves searching for all occurrences of a value in a randomly selected array, addressing the key question of the algorithm's expected time complexity. By presenting tasks that demonstrate the practical application of expectation, we aim to equip students with the tools needed to make informed decisions when designing and optimizing algorithms.
– Name: AbstractInfo
  Label: Abstractor
  Group: Ab
  Data: As Provided
– Name: DateEntry
  Label: Entry Date
  Group: Date
  Data: 2026
– Name: AN
  Label: Accession Number
  Group: ID
  Data: EJ1494361
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=eric&AN=EJ1494361
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1111/test.12402
    Languages:
      – Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 9
        StartPage: 3
    Subjects:
      – SubjectFull: Programming
        Type: general
      – SubjectFull: Expectation
        Type: general
      – SubjectFull: Computer Science Education
        Type: general
      – SubjectFull: Probability
        Type: general
      – SubjectFull: Efficiency
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Experiential Learning
        Type: general
      – SubjectFull: Problem Solving
        Type: general
      – SubjectFull: Difficulty Level
        Type: general
      – SubjectFull: Task Analysis
        Type: general
      – SubjectFull: Design
        Type: general
    Titles:
      – TitleFull: Practical Programming Tasks for Better Understanding of Expectation in Computer Science Probability Courses
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Nili Beck
      – PersonEntity:
          Name:
            NameFull: Yelena Stukalin
      – PersonEntity:
          Name:
            NameFull: Sigal Levy
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 0141-982X
            – Type: issn-electronic
              Value: 1467-9639
          Numbering:
            – Type: volume
              Value: 48
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Teaching Statistics: An International Journal for Teachers
              Type: main
ResultId 1