CS1
Random Number Generation ; Arrays ; Simulation/Calculation

(Insect Garden (XNA) ; Monte Carlo Integration (Console) )

 
Key Topics That Students Will Learn In This Assignment:
  1. Function Decomposition
  2. Algorithm Implementation
  3. Arrays (this last topic can be optional)
Pre-requisite Knowledge That Students Must Know, Prior To Starting This Assignment:

(What students must know in order to able to complete this assignment)

  • Flow Control: conditional selection (if statements)
  • Flow Control: iteration (loops)
  • Simple/Primitive Variables: int, double (etc)
  • Random number generation
  • Math: Distance Formula Between Two, 2D Points
  • Console version: Basic Console Input/Output
  • XNA Version: instance variables
    • (to hold data between calls to UpdateWorld)
Summary

For the Console version, students will code a simple, brute-force 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 pre-defined, 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 (pre-defined, 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 on-screen, and capture insects for points.  The game-play will consist of an individual insect (out of a collection of different types of insects) appearing at a random place on-screen, and then semi-randomly 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 point-values (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.
Pre-Test Post-Test
Lecture Hours Prior To Assignment Due Date: 15-20
ACM Classification (Topics Covered):

(What the students will learn, and demonstrate, by doing this assignment)

 

From:
 

Computing Curricula 2001

Computer Science

Final Report
(December 15, 2001)


written by
 

The Joint Task Force on Computing Curricula
IEEE Computer Society
Association for Computing Machinery

 

PF1. Fundamental programming constructs

  • Basic syntax and semantics of a higher-level language

  • Variables, types, expressions, and assignment

  • Simple I/O

  • Conditional and iterative control structures

  • Functions and parameter passing

  • Structured decomposition

AL2. Algorithmic strategies

  • Brute-force algorithms

  • Numerical approximation algorithms

Technical Requirements:

(What the students will learn, and demonstrate, by doing this assignment)

 

From:
 

Computing Curricula 2001

Computer Science

Final Report
(December 15, 2001)


written by
 

The Joint Task Force on Computing Curricula
IEEE Computer Society
Association for Computing Machinery

 

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.

Since they're coding from scratch, I think they're doing this with their own programs (as they write the programs, part-by-part), but it's not so much like they're being given code & then modifying it.
 

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.

It will be impossible to complete the assignment without the first three items.  Using functions will result in substantially higher-quality code.

 

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 problem-solving

PF2.1 - Discuss the importance of algorithms in the problem

PF2.2 - Identify the necessary properties of good algorithms.
(After completing this assignment, students should be able to do meet the above objectives, but they are not required to actually demonstrate these in any way)


PF2.3 - Create algorithms for solving simple problems

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.
Many students will be tempted to track all of the points in an array, or to generate a Point object per point (if they're ahead, and know some OOP), but these are inefficient constructs

 

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.