
CS2 ( Alphabet Here (XNA) ; BST Implementation (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 both versions, the students will implement a Binary Search Tree (BST)
class that provides two 'categories' of functionality. The first
category is basic functionality like adding a value to the tree,
searching the tree for a given value, and for printing all the elements
within the tree. The second category is more advanced
functionality, and consists of methods to determine the height of the
tree, to clone the tree (this makes a deep copy of the structure of the
starting tree  not just readding all the values to a second tree), and
to balance the tree in O(N * lg(N) ) time, using a helper array of O(N)
size. One strategy for covering/lecturing the material that this assignment deals with is to actually cover Add, Find, and Print inclass (for example, to explain actual working code samples inlecture), and to then use this assignment for force the students to reimplement that functionality. Then, use the second category of functionality to go beyond those basics, and to ask students to extend what they've been shown with new, novel methods that they'll implement. Note: the XNA version demonstrates how to implement a tree with most of the logic in the BST nodes, while the example solution for the console version demonstrates how to create a binary search tree with most of the logic in the BST class itself. For the Console version, the students will implement the BST class as specified in the assignment, and will then either produce test code to fully exercise the class, or else produce a console based, menudriven program that will allow them to fully test the class in a more adhoc manner. It's also an option to give them one (or both) pieces so that they can focus on the BST implementation, if the instructor desires. For the XNA version, the students the students will implement the
BST class as specified in the assignment, and will then use that
implementation to complete the provided game. 
Instructor F.A.Q.  
PreTest  PostTest 
Lecture Hours Prior To Assignment Due Date:  1020 
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
PF3. Fundamental data structures
PL6. Objectoriented programming
AL1: Basic algorithmic analysis

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. Since the students are given the existing code, but aren't given a detailed explanation for how it works, they will have to demonstrate that they have developed an understanding of the program by extending it
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. This is largely provided to the students, in the sense that there isn't a lot of extra functions needed. However, they do need to be able comprehend the existing structure of the provided code, including the functional decomposition inherent in that design.
Programming Fundamentals:: Fundamental data structures PF3.2  Describe how the data structures in the topic list are allocated and used in memory. This is largely provided to the students, in the sense that there isn't a lot of extra functions needed. However, they do need to be able comprehend how the various objects are allocated, so that they can correctly implement code like the Clone method (as opposed to them incorrectly reassigning all the references in an existing tree, for example)
PF3.4  Implement the userdefined data structures in a highlevel language. The focus of the assignment is to implement a binary search tree, in C#.
PF3.6  Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables. The focus of the assignment is to implement a binary search tree, which is not listed above, but is a related structure, and one that is commonly covered in a course that covers the above topics. Programming Fundamentals: Recursion PF4.5  Implement, test, and debug simple recursive functions and procedures.. The students will need to use recursion for the printing, cloning, balancing, and heightfinding routines that they are asked to create. Algorithms and Complexity: Basic algorithmic analysis AL1.3  Determine the time and space complexity of simple algorithms. The students are (optionally) told to implement operations on their BST using the Big 'Oh' notation, so they must be able to determine the time & space complexity of their implementation, in order to know if the implementation is in compliance with the constraints set forth in the homework assignment. Note that students will be expected to analyze their algorithms specifically in regard to BOTH time and space. Algorithms and Complexity: Algorithmic Strategies AL2.4  Implement a divideandconquer algorithm to solve an appropriate problem. All of the more advance methods (the Clone, Balance, and FindDepth) methods must be implemented using a recursive, divideandconquer algorithm; the method that prints all the values in order must also be implemented using a recursive, divideandconquer algorithm. Programming Languages: ObjectOriented Programming PL6.2  Design, implement, test, and debug simple programs in an objectoriented programming language. This assignment requires the
students to understand and utilize encapsulation. PL6.3  Describe how the class mechanism supports encapsulation and information hiding. The students are not directly
asked to describe this, but they are required to mark their data
fields / methods with the appropriate access restriction.
