CS2
Binary Search Trees

( Alphabet Here (XNA) ; BST Implementation (Console) )

 
Key Topics That Students Will Learn In This Assignment:

 

  • Binary Search Trees - Basic Operations
    (basic operations like Add, Find, and Print (all elements, in order))
  • Binary Search Trees - Advanced Operations
    (additional / non-traditional operations like finding the height of a tree, cloning a tree, and balancing a tree using an (inefficient) supplementary array (which will require O(N) space ))
  • XNA Only: Using the List<char> class
    (This is presented quickly and superficially - it's very easy to use, and useful within the XNA version of the project)
Pre-requisite Knowledge That Students Must Know, Prior To Starting This Assignment:

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

  • Simple/Primitive Variables: int, double (etc)
  • Operators
  • Flow Control: conditional selection (if statements)
  • Flow Control: iteration (loops)
  • Object-Oriented Programming
    • Encapsulation
    • 'Basics' (data fields, methods)
    • References to objects (including null)
    • This Assignment does NOT require inheritance, polymorphism, or generics/templates
  • OPTIONAL: Big 'Oh' Notation is used to describe required running time
    • This could be replaced with a longer, English description, if needed
  • Console version:OPTIONAL: Test Driven Development could be covered
    • The student starter solution, and the example solution, both include a full suite of tests for the class(es) that the students implement.  The instructor could remove these, or probably cover what the students need to know in about 10 minutes.
  • Console version: Basic Console Input/Output
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 re-adding 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 in-class (for example, to explain actual working code samples in-lecture), and to then use this assignment for force the students to re-implement 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, menu-driven program that will allow them to fully test the class in a more ad-hoc 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.
For the XNA version, there is the possibility of removing some (fairly simple) code to draw the BST on the screen, which could be left as an exercise for students seeking more direct experience with video game programming.

  Instructor F.A.Q.
Pre-Test Post-Test
Lecture Hours Prior To Assignment Due Date: 10-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

PF3. Fundamental data structures

  • Primitive types
  • Records
  • Strings and string processing
  • Data representation in memory
  • Static, stack, and heap allocation
  • Runtime storage management
  • Pointers and references
  • Linked structures
  • Implementation strategies for stacks, queues, and hash tables
  • Strategies for choosing the right data structure

PL6. Object-oriented programming

  • Object-oriented design

  • Encapsulation and information-hiding

  • Separation of behavior and implementation

  • Classes and subclasses

AL1: Basic algorithmic analysis

  1. Big O, little o, omega, and theta notation
 
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.

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.

The primary goal of the assignment is to modify the code that's provided by the instructor
 

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 these items.

 

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 user-defined data structures in a high-level 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 height-finding 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 divide-and-conquer algorithm to solve an appropriate problem.

All of the more advance methods (the Clone, Balance, and FindDepth) methods must be implemented using a recursive, divide-and-conquer algorithm; the method that prints all the values in order must also be implemented using a recursive, divide-and-conquer algorithm.

Programming Languages: Object-Oriented Programming

PL6.2 - Design, implement, test, and debug simple programs in an object-oriented 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.
 

 


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.