Data Structures 1

Last modified: February 24 2009 01:12:37 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

The groups consist of three people all of whom are supposed to be attending the same recitation section. If for some reason, you are not attending that particular recitation section, please let me know (IMMEDIATELY) and we can adjust groups. In some cases, there are groups of two. Special instructions are given for the groups of two in the description below.

Tuesday Recitation Groups

Wednesday Recitation Groups

Thursday Recitation Groups

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
• Adding functionality on to an exisiting data structure (written by another group member)

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 1 Assignment

Meet your group members - talk to them prior to recitation - email, exchange other contact information. Meet face to face in recitation and discuss the assignment and any other details. For this first week, you should not meet as a group to discuss the coding that you are doing. Each group member should work independently on this stage. You will bring the results of this week together next week and begin some of the group discussion.

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

You are to complete the implementation of a circular, doubly-linked list. The header file that includes the functions you are to implement is available here (Node.h here). Put the header file with your implementation into a directory named CircleDoubleList. You will zip up this directory and create a CircleDoubleList.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.

Group Member 2

You are to complete the implementation of an array-based binary search tree. The header file that includes the functions you are to implement is available here. Put the header file with your implementation into a directory named BinarySearchTree. You will zip up this directory and create a BinarySearchTree.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.

Group Member 3

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.

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.