Abstract

The concept of expectation plays a pivotal role in computer science education, particularly when evaluating the time efficiency of algorithms. However, the gap between theoretical understanding and practical application often hinders students' ability to grasp the significance of expectation in real-world scenarios. This paper aims to bridge this gap by exploring the importance of expectation in computer science education and presenting two written tasks the students were given that demonstrate its practical application. The tasks are designed to engage students in hands-on learning experiences, enabling them to apply the concept of expectation to real-world problems.
Task A, "The number of successes of the careless clerk," simulates a scenario where a careless mailing clerk randomly inserts letters into envelopes without considering their intended recipients. By generating random permutations and counting the number of correctly placed letters, students calculate the average number and variance of successes for different values of n. This experiment allows students to explore the expected outcome of the clerk's actions and gain a deeper understanding of expectation in a practical context.
Task B, "Linear Search vs. Binary Search", focuses on comparing the efficiency of two search algorithms. Students initialize an array with values drawn from a discrete uniform distribution, generate many additional values, and search for these values using both linear and binary search algorithms. By recording the average number of comparisons made by each search method, students assess the efficiency of the algorithms for different array sizes. This hands-on approach reinforces the theoretical concepts and provides students with practical experience in evaluating algorithm efficiency.
Through these tasks, we demonstrate the possibility of integrating concepts in probability with concepts in programming as part of statistics and probability education for computer science students. By engaging students in practical learning experiences and providing them with the opportunity to apply calculations of expectation in real-world scenarios. These tasks seek to enhance their understanding of this fundamental concept and its relevance in algorithm analysis and design.
This paper's contribution lies in its approach to bridging the gap between theory and practice in statistics and probability education. By presenting tasks that showcase the practical application of expectation, we aim to equip students with the necessary tools to make informed decisions when designing and optimizing algorithms. This approach fosters a deeper understanding of statistics and probability in the context of computer science education and prepares students for real-world challenges.