Data Structures 2

Last modified: February 20 2009 02:17:03 PM

The Data Structures Exercises will be completed in groups assigned by the instructor. If you are experiencing group problems, please seek out the advice of your instructor.

Group Assignments - Same as Data Structures 1 Assignment

Assignment

In the course of the next four weeks, each group member will complete each of the following tasks:

• Creating an implementation for a particular data structure
• Writing a program that can test the functionality of a particular data structure
• Combine the results above and ensure that the implementation and testing of the data structure is complete

Each week, there is a new part of the assignment to be completed. Assume that you have one week for each part of the assignment. That is, do your assignment as though it is due the following week in recitation. Use recitation time to discuss issues and concerns related to the part you just completed or the part upcoming this week, and then use the last week of the assignment due dates to clean things up and submit. All of the submissions are due the Friday before spring break. However, you could realistically be finished almost a week before that if you complete the assignments on the schedule I'm suggesting.

Week 2 Assignment

There are three members of your group listed in the charts in a particular order, consider that group member 1 is the first member, group member 2 the second and group member 3 is the third. (If you only have two members, then you only have group member 1 and group member 2 - you do not need to complete the work for group member three). The assigments for each group member this week are as follows.

Group Member 1 (if group has 2 or 3 members)

You are to complete a testing program for an array-based binary search tree. The header file that includes the functions that you are to test is available here. Your testing program should be named BinarySearchTreeTest.cpp. Your program should ensure that all of the functions outlined in the header file work properly. This program MUST NOT be interactive. The testing that the list goes through is to be outlined in the series of function calls in the program.

You are to complete a report about the test cases for the functions and put it in a file named BinarySearchTreeTestPlan.txt. This report should outline what cases are tested in the testing program and what the expected results are if the tree code that it is tested upon is properly implemented.

You will place your C++ file and the test plan file in a directory named BinarySearchTreeTest. You will zip up this directory and create a BinarySearchTreeTest.zip and submit it by the due date. You are responsible for the submission of this part of the data structures project.

Group Member 2 (if group has 3 members)

You are to complete a testing program for a stack (if group number is odd) or queue (if group number is even). The header file that includes the functions for the stack that you are to test is available here (CircleDoubleList.h here). The header file that includes the functions for the queue that you are to test is available here (CircleDoubleList.h here).

Your testing program should be named StackTest.cpp or QueueTest.cpp as appropriate. Your program should ensure that all of the functions outlined in the header file work properly. This program MUST NOT be interactive. The testing that the list goes through is to be outlined in the series of function calls in the program.

You are to complete a report about the test cases for the functions and put it in a file named StackTestPlan.txt or QueueTestPlan.txt. This report should outline what cases are tested in the testing program and what the expected results are if the stack/queue code that it is tested upon is properly implemented.

You will place your C++ file and the test plan file in a directory named StackTest or QueueTest. You will zip up this directory and create a StackTest.zip or QueueTest.zip and submit it by the due date. You are responsible for the submission of this part of the data structures project.

Group Member 2 (if group has 2 members)

You are to complete a testing program for a circular, doubly-linked list. The header file that includes the functions that you are to test is available here (Node.h here). Your testing program should be named CircleDoubleListTest.cpp. Your program should ensure that all of the functions outlined in the header file work properly. This program MUST NOT be interactive. The testing that the list goes through is to be outlined in the series of function calls in the program.

You are to complete a report about the test cases for the functions and put it in a file named CircleDoubleListTestPlan.txt. This report should outline what cases are tested in the testing program and what the expected results are if the list code that it is tested upon is properly implemented.

You will place your C++ file and the test plan file in a directory named CircleDoubleListTest. You will zip up this directory and create a CircleDoubleListTest.zip and submit it by the due date. You are responsible for the submission of this part of the data structures project.

Group Member 3

You are to complete the implementation of a stack (if your group number is odd) or a queue (if your group number is even). The header file that includes the functions for the stack that you are to test is available here (CircleDoubleList.h here). The header file that includes the functions for the queue that you are to test is available here (CircleDoubleList.h here).

It is more than likely that the current implementation of the CircleDoubleList is not satisfactory for completing either a stack or a queue. You are allowed to ask the implementer of your group's CircleDoubleList to implement one (and only one) additional method that will help you in your task. That group member should include the method in the code that he/she submits for this assignment.

Put the header file with your implementation into a directory named Stack or Queue. You will zip up this directory and create a Stack.zip or Queue.zip and submit it by the due date. You are responsible for the submission of this part of the data structures project.

You should not create any testing code for you implementation and you should not test your implementation in any significant way. If you want to test out the idea for an algorithm in a main function, that is fine, but do not attempt to uncover errors or omissions in the code you wrote. That is the job of another person in your group.

What to submit

For each member of the group, what needs to be submitted is outlined in the description above. Make sure that the submissions contain the appropriate files.

You need to submit your files using the Web-CAT system. For more information about using Web-CAT, please see: http://www.cse.buffalo.edu/faculty/adrienne/SP2009/cse250/Lectures/SubmissionUsingWeb-CAT.ppt

Due Date

All three data structures assignments are due to be turned in by 11:59:59pm on Friday, March 6th.