
CS1 (Insect Garden (XNA) ; Monte Carlo Integration (Console) ) 
Key Topics That Students Will Learn In This Assignment: 

Prerequisite Knowledge
That Students Must Know, Prior To Starting This Assignment: (What students must know in order to able to complete this assignment) 

Summary 
For the Console version, students will code a simple, bruteforce algorithm that will approximate the area of a circle. The ostensible goal is for them to generate a table of results, that display the results of the approximation, as well as showing the actual area of the circle. This is can be called 'Monte Carlo' integration, and is done by randomly picking a point in a predefined, limited space, and asking "Is that point inside the circle?". By repeatedly picking a point at random, potentially thousands and thousands of times, one can obtain a reasonably accurate approximation of the true area of the circle by multiplying the percentage of points that landed inside by the circle by the total area of the (predefined, limited) space. Author's Note: In my class, this is the first simulation that's fairly abstract. Unlike many programming assignments that rely on a fairly straightforward mapping between classes/constructs and the problem that's being dealt with, this assignment requires them to step back, and think about how they can achieve their goals in a minimum amount of memory. For the XNA version, students will code parts of a simple, limited game in which the player will run around onscreen, and capture insects for points. The gameplay will consist of an individual insect (out of a collection of different types of insects) appearing at a random place onscreen, and then semirandomly wandering around for a limited period of time. If the player doesn't capture the insect (before the time runs out), then the insect disappears. If the player captures the insect before the time runs out, then the player is awarded points (based on the type of the insect), and the player is told how many insects have appeared, how many the player has captured, what the percentage of the total number of insects have been captured, what the average number of points for all the captured insects are, and what the first five recent pointvalues (for captured insects) have been. Whether the player has captured the current insect or not, a new insect will appear for the player to try and capture. 
Instructor F.A.Q.  
PreTest  PostTest 
Lecture Hours Prior To Assignment Due Date:  1520 
ACM Classification (Topics Covered): (What the students will learn, and demonstrate, by doing this assignment)
From: Computing Curricula 2001 Computer Science — Final Report —
The Joint Task Force on Computing Curricula

PF1. Fundamental programming constructs
AL2. Algorithmic strategies

Technical Requirements:
(What the students will learn, and demonstrate, by doing this assignment)
From: Computing Curricula 2001 Computer Science — Final Report —
The Joint Task Force on Computing Curricula
It is hoped that providing this information may help instructors with the accreditation process, as calling this information out will help clarify how this assignment (and from here, the overall course) meets the learning outcomes for the overall program/department, and institution. 
Programming Fundamentals: Fundamental programming constructs
PF1.1  Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit. Students need to do this as they code. For example, as they run into problems, they'll need to explain (to themselves, if nothing else) what their program is doing, in order to figure out how to fix problems.
PF1.2  Modify and expand short programs that
use standard conditional and iterative control structures and
functions. PF1.3  Design, implement, test, and debug a
program that uses each of the following fundamental programming constructs: basic
computation, simple I/O, standard conditional and iterative
structures, and the definition of functions.
PF1.4  Choose appropriate conditional and iteration constructs for a given programming task. It will be impossible to complete the assignment without this.
PF1.5  Apply the techniques of structured (functional) decomposition to break a program into smaller pieces. In my classes, since students get to do an initial version, then revise that & submit it a second time, the 'second iteration' often ends up being a time when functional decomposition is emphasized. While it is possible to complete the entire assignment in main, most students find it substantially easier to deal with by creating auxiliary functions.
Programming Fundamentals: Algorithms and problemsolving PF2.1  Discuss the importance of algorithms in the problem PF2.2  Identify the necessary
properties of good algorithms.
In this assignment, the students will normally have seen the mathematical distance formula first, but they still need to figure out how to use that (and the definition of a circle) to actually determine whether a given, randomly placed point, is inside the circle or not.
Programming Fundamentals: Fundamental data structures
PF3.6  Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables. Students will work with arrays, but none of the other data structures
PF3.8  Choose the appropriate data structure
for modeling a given problem.
Algorithms and Complexity: Algorithmic strategies PF2.8  Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial. This summarizes the ostensible goal of the assignment nicely :)

This document and the related materials are developed with support
from Microsoft Research Computer Gaming Initiative under the Computer Gaming
Curriculum in Computer Science RFP, Award Number 15871.