Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI2270: Final Project

Objectives

1. Research a data structure of your choice from a list of options

2. Implement the data structure you chose

3. Create a program using that data structure to illustrate its benefits and weaknesses

4. Communicate your findings

Instructions

To earn credit for this assignment, you must submit your code to GitHub by the deadline. You will also need to submit your project proposal and report to Canvas. We will be conducting grading interviews for this project. Be sure to sign up for and attend your grading interview. Failure to attend a grading interview will result in a 0 on the code submission and grading interview portions of the project!

Problem Statement

For this project, you will explore one of the data structures we discussed in the last few weeks of class. To get full points on the project, you must complete the steps below. These steps are explained in more detail in later sections.

1. Pick your project. Review the list of possible data structures and pick the data structure you would like to explore in more detail.

2. Research your data structure. Use class notes, the textbook, and online resources to learn more about your data structure.

3. Design your project. Write a short project proposal summary describing the data structure you chose and what steps you will need to take to finish the project.

4. Implement your data structure. Implement the data structure and write a small program to test the functionality of your data structure.

5. Share your findings. Write a short report about your data structure and attend a grading interview.

Code Organization

For this project, you will be responsible for organizing your own code. You are welcome to use the file structure from the assignments as a starting point. However you choose to organize your code, you must upload any code files you use to GitHub for grading. You must also update the README.md file on GitHub to specify how the course staff ought to compile and run your code. Anything not submitted to GitHub will not be considered during the grading of your project.

Step 1: Pick your Project

You may choose one data structure to explore in more detail from the list below. Review the minimum implementation requirements section below for more details about each data structure.

1. Red-black trees

2. Hash tables

3. Heaps & priority queues

Step 2: Research your Data Structure

You may use class notes, the textbook, and online resources to learn more about your data structure. Be sure to keep track of your sources, so that you can cite them in your project proposal and report. Here are some questions you should answer while researching your data structure:

1. At a conceptual level, what is this data structure?

2. How is this data structure typically implemented?

3. What are common operations on this data structure (e.g., rotations on red-black trees)?

4. What is the time complexity (Big-O) of those common operations?

5. When and where is this data structure used?

6. When would somebody want to use this data structure over other options?

7. When would this data structure not provide an advantage?

Step 3: Design your Project

Write a short project proposal describing the data structure you chose and what steps you will need to take to finish the project. Your project proposal should have the following sections:

1. An introduction describing the data structure you plan on researching.

2. A summary of your findings so far, which should answer at least six of the questions from above.

3. An outline of the code you will need to write for the project. This should include a list of member methods you will need to implement in order to have a working demonstration of your data structure (e.g., will you need to implement a leftRotate function for your red-black tree?).

4. A brief description of how you intend to use your data structure in your final program. In other words, describe how you plan to test your data structure.

5. A list of external libraries and other references you plan on using in the implementation of your project.

6. A description of any potential difficulties you foresee in the completion of your project.

7. A bibliography or works cited describing the sources you have referred to thus far in your work.

You may choose to format your proposal as an essay or as a list of bullet points. Pictures are also allowed. So long as your work is clear, and the questions above have been addressed, how you format your proposal does not matter.

Step 4: Implement your Data Structure

Implement your data structure and write a small program demonstrating how it is used. More details about what you are expected to implement are given in the “Minimum Implementation Requirements” section below.

You should implement your data structure as a class, and you should make use of the data structure in your main program. A good starting place for creating your main program is the homework assignments. The point of your program should be to demonstrate the unique attributes and behaviors of your data structure. For example, if you are implementing a priority queue, you could create a program to schedule tasks based on urgency.

Step 5: Share your Findings

Share your findings by creating a small report and attending interview grading. In your report, your report must address the following:

1. Describe your data structure at the conceptual level.

2. Explain what the typical operations on your data structure are. Include a discussion of the time complexity (Big-O) of the operations.

3. Describe how your data structure is typically used.

4. Discuss any weaknesses or constraints of your data structure.

5. Discuss any difficulties or weaknesses of your implementation of the data structure.

6. Discuss what you learned from this project, and what accomplishment you are most proud of.

7. Include a bibliography or works cited.

You may choose to format your report as an essay or as a list of bullet points. Pictures are also allowed. So long as your work is clear, and the points above have been addressed, how you format your report does not matter.

You may refer to your code at any point in the report (e.g. “In my printTree function, I…”). There is no length requirement to the report. It is intended to prepare you for interview grading.

You will also need to sign up for a grading interview with a member of the course staff. Grading interviews will be conducted during the last Wednesday and Thursday of the semester. You may wait to submit your report until after your interview is over.

Interview Grading

You must sign up for a ten-minute grading interview with a member of the course staff. During this interview, you will be asked to present your code to the interviewer. It is expected that you will be able to explain your code in detail. The interviewer will ask you specific questions about the code that you wrote and general questions about the data structure you chose to implement.

Minimum Implementation Requirements

The minimum implementation requirements vary depending on the data structure you choose to study. While you are welcome to implement additional functionality (e.g., a peek function for your priority queue), you are not required to do so. Your code should not have any memory leaks.

Data Structure	Minimum Functionality	Notes
Red-black trees	· Node insertion · Tree balancing (rotations and recoloring) · A method to print the entire tree (with colorings)	None
Hash tables	· Element insertion, retrieval, and removal · Collision handling through open addressing or chaining · A method to print the entire hash table	· Hash function must be implemented yourself · Collision avoidance must be implemented yourself · You may not use the vector library to implement your hash table.
Heaps & priority queues	· Must implement a priority queue with a heap · Support push and pop · A method to print the entire heap in order	· You may use the vector library in the implementation of your heap · You may not use any pre-implemented sorting methods to achieve heap behavior.

Overall Grade Allocation

· Proposal (10%)

· Code submission (20%)

· Grading interview (60%)

· Report (10%)

Rubrics

Individual rubrics for each portion of the assignment are available on Canvas.

Guidelines for External Libraries and Outside Sources

First and foremost, you must cite any outside source that you consult while working on this project. If you plan on using an external library, you must include a citation in your project report. If you consult an outside source for help in implementing a particular algorithm or piece of code, you must cite the source in your code and in your project report. The use of generative AI models (e.g. ChatGPT) for writing code will be permitted on this project. However, you must cite the AI model you used in your code and in your report. You must also be able to explain and analyze all of the code that you submit.

Citing Generative AI Models

To properly cite ChatGPT or other generative AI models, you must:

1. Include the version of the model you are using

2. Include the verbatim prompt that you gave to the model

3. Include the date you accessed the model

Example:

/** From ChatGPT v. 3.5: “Write C++ code to bubble sort an array of floats” on July 5 2025

*/

void bubbleSort(float arr[], int size)

{

//…

}