Homework #2 – Notebook

CS300 
Homework #2 – Notebook
Brief Description
In this homework, you will implement two “Notebooks” by using the AVL Search Tree and the
Binary Search Tree (BST). Additionally, you will display the speed of some of the operations on
these tree data structures that are used for the implementation. Each “Notebook” will have a
nested tree structure, which will be explained in more detail in the rest of the documentation.
Although each Notebook tree will have a separate implementation, they will store the same
data and will perform the same operations. Basically, the only difference between the
Notebooks will be the data structures that are going to be used for the implementation. Each
Notebook will contain multiple sections and each section will have multiple items which will
store the information inside.
A notebook will have a nested structure as follows:
❏ Notebook
May have one or many section/s.
❏ Section
Will have a title.
May have one or many item/s.
❏ Item
Will have a title.
Will have information.
Example Notebook:
Courseworks
CS300-the homework is due Sunday
CS408-don't forget the quiz
CS303-16:40 office hour
Movies
The Holy Mountain-7.9
I Lost My Body-7.6
Phonebook
Gulsen-09990000099
Alp-09998765432
Furkan-09876543210
Serra-09898989898
As seen in the example above, a notebook is a tree of sections. Each section has got a title
string and a tree of items. Each item has a title string and an information string.
There cannot be two sections with the same title inside the same notebook. Also, there
cannot be two items with the same title inside the same section.
BST and AVL Tree
You are going to implement a BST class and an AVL Tree class. Which will get used separately
to implement two different notebooks that will perform the same operations over the same
data. You CANNOT USE VECTOR OR ARRAY to implement the notebooks. Also, you cannot use
a BST inside an AVL Tree and vice versa. In other words, there will be two notebooks, one of
them will be implemented by using nested AVL Trees and the other will be implemented by
using the nested BSTs only.
Both the BST and the AVL Tree classes should be reusable for different types, classes, etc.
Thus, both the BST and AVL Tree classes MUST be template-based classes.
Use the “title” properties of the section and the item to compare the nodes inside the trees.
Program Flow
❏ Initializing the notebooks
At the very beginning of the program, you should create two notebooks (one by using
the BST, other by using the AVL Tree).
Then, your program will read a text file that contains the section and item data of the
notebook. Your program will insert the data into the notebooks accordingly.
Your program will display the elapsed insertion time of each section for both of the
notebooks. Then the program will direct to the main menu.
❏ Main menu
On the main menu, there will be 6 options. The user will enter an input between [1-6]
then the program will perform the commands on both notebooks accordingly. These
options are:
1. Display the sections (AVL)
Your program should perform an inorder traversal over the AVL notebook and
print the section titles in ascending order (alphabetically).
2. Display the sections (BST)
Your program should perform an inorder traversal over the BST
notebook and print the section titles in ascending order (alphabetically).
3. Select a section
The program will get a section title name from the user then it will search for
the section with the same title, both in the AVL and BST notebooks.
If there exists no such section your program will display an error. Else it will
direct to the section menu to perform operations on the selected section.
4. Add new section
Get a title input from the user. If a section with the given title already exists in
the notebook, display an error message. Else, create a new section with that
title and insert it into the notebooks.
5. Delete a section
Get a title input from the user. If a section with the given title does not exist in
the notebook, display an error message. Else, remove the section with that title
from the notebooks.
6. Exit
Terminate the program.
❏ Section menu
At option 3 of the main page, if the title of any section matches with the input from the
user, the program should land on the section menu page to perform operations on the
selected section.
On the main menu, there will be 7 options. The user will enter an input between [1-7]
then the program will perform the commands on both notebooks accordingly. Options
are:
1. Display the items (AVL)
For the selected section of the AVL notebook:
Your program should perform an inorder traversal over the items tree of the
section and print the item titles in ascending order (alphabetically).
2. Display the items (BST)
For the selected section of the BST notebook:
Your program should perform an inorder traversal over the items tree of the
section and print the item titles in ascending order (alphabetically).
3. Display the information of an item
Get an item title input from the user. If an item with the given title does not
exist in the notebook, display an error message. Else, display the information of
the matching item.
Note: Although, you should make a query on both the AVL notebook and the
BST notebook you can display the matching item information once. Since, if
your program works correctly, matching item information of the AVL notebook
and the BST notebook will be the same.
In both cases, display the elapsed query/insertion time for the AVL notebook
and the BST notebook.
Display the elapsed query time.
4. Add a new item
Get an item title input from the user. If an item with the given title already
exists in the section, display an error message. Else, create a new item with that
title and insert it into the selected section.
In both cases, display the elapsed query/insertion time.
5. Update the information of an item:
Get an item title input from the user. If an item with the given title does not
exist in the section, display an error message. Else, get the new information
from the user and update the information of the item accordingly.
Display the elapsed query/update time.
6. Delete an item
Get an item title input from the user. If an item with the given title does not
exist in the section, display an error message. Else, remove the item with that
title from the section. Display the elapsed deletion time.
7. Return to main menu
Go back to the main menu.
Text File
As mentioned before we have provided initial data to fill the notebooks at the beginning of
the program. You should read the data from a text file (.txt extension) and insert it into the
notebooks accordingly.
The text file will contain the following 3 sections:
- Courseworks: contains 5 non-sorted items.
- Movies: contains +90000 non-sorted items.
- Phonebook: contains +6000 sorted items.
❏ Data format
If the first character of a line is not a ‘-‘ (dash), it is the title of a new section. Until the
occurrence of a new section, as long as a new line starts with a dash it denotes the
item of the given section. Each item line contains exactly two dashes. The first one
denotes that it is an item line and the second one separates the item title from the
item info.
So, a text file with notebook data inside it will look like the following:
Section title 1
-item title 1-item info 1
-item title 2-item info 2
-item title 3-item info 3
Section title 2
-item title 1-item info 1
-item title 2-item info 2
Example text file:
Courseworks
-CS300-the homework is due Sunday
-CS408-don’t forget the quiz
-CS303-16:40 office hour
Movies
-The Holy Mountain (1973)-7.9
-Climax-7
-Midsommar-7.6
Elapsed Time
You should display the elapsed time of the notebook operations. For that purpose, you can use
the C++ built-in library chrono. You can include the library by using #include <chrono>.
You are recommended to use chrono::high_resolution_clock to obtain accurate results.
Documentation: https://en.cppreference.com/w/cpp/chrono/high_resolution_clock
Here is an example to get the time duration of a foo() function in microseconds:
Between the start and the end clocks, you should only include the member functions of the
trees (insert, delete, update, etc.) and exclude the rest of the code (getline, loops, arithmetic
operations, etc.).
Sample Run
Welcome to the Notebook!
Section "Courseworks" has been inserted into the AVL notebook.
[AVL] Elapsed time: 15 microseconds
Section "Courseworks" has been inserted into the BST notebook.
[BST] Elapsed time: 7 microseconds
Section "Phonebook" has been inserted into the AVL notebook.
[AVL] Elapsed time: 18236 microseconds
Section "Phonebook" has been inserted into the BST notebook.
[BST] Elapsed time: 3864642 microseconds
Section "Movies" has been inserted into the AVL notebook.
[AVL] Elapsed time: 300933 microseconds
Section "Movies" has been inserted into the BST notebook.
[BST] Elapsed time: 353231 microseconds
MENU
Please enter an input between [1 - 6]:
1- Display the sections [AVL]
2- Display the sections [BST]
3- Select a section
4- Add new section
5- Delete a section
6- Exit
Input: 1
*****
Courseworks
Movies
Phonebook
*****
Input: 2
*****
Courseworks
Movies
Phonebook
*****
Input: 3
Enter the title of the section: Cour
Invalid title!
Input: 3
Enter the title of the section: Courseworks
Selected section -> Courseworks
Please enter an input between [1 - 7]:
1- Display the items [AVL]
2- Display the items [BST]
3- Display the information of a item
4- Add new item
5- Update the information of a item
6- Delete an item
7- Return to main menu
Input: 1
*****
CS300
CS303
CS408
ENS492
SPS303
*****
Input: 2
*****
CS300
CS303
CS408
ENS492
SPS303
*****
Input: 3
Enter the title of the item: CS100
[AVL] Elapsed time: 8 microseconds
[BST] Elapsed time: 2 microseconds
Invalid title.
Input: 3
Enter the title of the item: CS300
[AVL] Elapsed time: 6 microseconds
[BST] Elapsed time: 0 microseconds
the homework is due Sunday
Input: 4
Enter a title for the item: CS303
Item "CS303" already exists in the "Courseworks".
Input: 4
Enter a title for the item: CS600
Enter a description for the item: huh?
[AVL] Elapsed time: 14 microseconds
[BST] Elapsed time: 3 microseconds
The new item "CS600" has been inserted.
Input: 5
Enter the title of the item: CS999
[AVL] Elapsed time: 5 microseconds
[BST] Elapsed time: 2 microseconds
Item "CS999" does not exist in the "Courseworks".
Input: 5
Enter the title of the item: CS300
[AVL] Elapsed time: 6 microseconds
[BST] Elapsed time: 0 microseconds
Enter the new information: great
The content CS300 has been updated.
Input: 3
Enter the title of the item: CS300
[AVL] Elapsed time: 7 microseconds
[BST] Elapsed time: 1 microseconds
great
Input: 6
Enter the title of the item: CS123
Item "CS123" does not exist in the "Courseworks".
Input: 6
Enter the title of the item: CS300
[AVL] Elapsed time: 2 microseconds
[BST] Elapsed time: 2 microseconds
The item "CS300" has been deleted.
Input: 1
*****
CS303
CS408
CS600
ENS492
SPS303
*****
Input: 2
*****
CS303
CS408
CS600
ENS492
SPS303
*****
Input: 7
MENU
Please enter an input between [1 - 6]:
1- Display the sections [AVL]
2- Display the sections [BST]
3- Select a section
4- Add new section
5- Delete a section
6- Exit
Input: 4
Enter a title for the section: Courseworks
Section "Courseworks" already exists.
Input: 4
Enter a title for the section: Colors
The new section "Colors" has been inserted.
Input: 3
Enter the title of the section: Colors
Selected section -> Colors
Please enter an input between [1 - 7]:
1- Display the items [AVL]
2- Display the items [BST]
3- Display the information of a item
4- Add new item
5- Update the information of a item
6- Delete an item
7- Return to main menu
Input: 1
*****
*****
Input: 2
*****
*****
Input: 4
Enter a title for the item: Red
Enter a description for the item: Fav
[AVL] Elapsed time: 4 microseconds
[BST] Elapsed time: 1 microseconds
The new item "Red" has been inserted.
Input: 1
*****
Red
*****
Input: 2
*****
Red
*****
Input: 7
MENU
Please enter an input between [1 - 6]:
1- Display the sections [AVL]
2- Display the sections [BST]
3- Select a section
4- Add new section
5- Delete a section
6- Exit
Input: 1
*****
Colors
Courseworks
Movies
Phonebook
*****
Input: 2
*****
Colors
Courseworks
Movies
Phonebook
*****
Input: 5
Enter the title of the section: Course
Section "Course" does not exist.
Input: 5
Enter the title of the section: Courseworks
The section has been deleted.
Input: 1
*****
Colors
Movies
Phonebook
*****
Input: 2
*****
Colors
Movies
Phonebook
*****
Input: 3
Enter the title of the section: Phonebook
Selected section -> Phonebook
Please enter an input between [1 - 7]:
1- Display the items [AVL]
2- Display the items [BST]
3- Display the information of a item
4- Add new item
5- Update the information of a item
6- Delete an item
7- Return to main menu
Input: 3
Enter the title of the item: Aada
[AVL] Elapsed time: 2465 microseconds
[BST] Elapsed time: 0 microseconds
0016839979200
Input: 3
Enter the title of the item: Zyrie
[AVL] Elapsed time: 2302 microseconds
[BST] Elapsed time: 2276 microseconds
0017707501460
Input: 5
Enter the title of the item: Zyrie
[AVL] Elapsed time: 2410 microseconds
[BST] Elapsed time: 2327 microseconds
Enter the new information: 000000
The content Zyrie has been updated.
Input: 6
Enter the title of the item: Kadeem
[AVL] Elapsed time: 6 microseconds
[BST] Elapsed time: 878 microseconds
The item "Kadeem" has been deleted.
Input: 4
Enter a title for the item: Zxxy
Enter a description for the item: ???
[AVL] Elapsed time: 12 microseconds
[BST] Elapsed time: 2143 microseconds
The new item "Zxxy" has been inserted.
Input: 7
MENU
Please enter an input between [1 - 6]:
1- Display the sections [AVL]
2- Display the sections [BST]
3- Select a section
4- Add new section
5- Delete a section
6- Exit
Input: 3
Enter the title of the section: Movies
Selected section -> Movies
Please enter an input between [1 - 7]:
1- Display the items [AVL]
2- Display the items [BST]
3- Display the information of a item
4- Add new item
5- Update the information of a item
6- Delete an item
7- Return to main menu
Input: 3
Enter the title of the item: Zingaresca
[AVL] Elapsed time: 31739 microseconds
[BST] Elapsed time: 2 microseconds
6.6
Input: 5
Enter the title of the item: Aurora
[AVL] Elapsed time: 30734 microseconds
[BST] Elapsed time: 2 microseconds
Enter the new information: cool
The content Aurora has been updated.
Input: 6
Enter the title of the item: Redskin
[AVL] Elapsed time: 8 microseconds
[BST] Elapsed time: 1 microseconds
The item "Redskin" has been deleted.
Input: 7
MENU
Please enter an input between [1 - 6]:
1- Display the sections [AVL]
2- Display the sections [BST]
3- Select a section
4- Add new section
5- Delete a section
6- Exit
Input: 6
General Rules and Guidelines about Homeworks
The following rules and guidelines will apply to all homework unless otherwise noted.
How to get help?
You may ask questions to TAs (Teaching Assistants) of CS300. Office hours of TAs can be found here.
Recitations will partially be dedicated to clarifying the issues related to homework, so it is to your benefit
to attend recitations.
What and Where to Submit
Please see the detailed instructions below/on the next page. The submission steps will get natural/easy for
later homework.
Grading and Objections
Careful about the semi-automatic grading: Your programs will be graded using a semi-automated system.
Therefore, you should follow the guidelines about input and output order; moreover, you should also use
the exact same prompts as given in the Sample Runs. Otherwise, the semi-automated grading process will
fail for your homework, and you may get a zero, or in the best scenario, you will lose points.
Grading:
❑ Late penalty is 10% off the full grade and only one late day is allowed.
❑ Having a correct program is necessary, but not sufficient to get the full grade. Comments,
indentation, meaningful and understandable identifier names, informative introduction and
prompts, and especially proper use of required functions, unnecessarily long programs
(which is bad) and unnecessary code duplications will also affect your grade.
❑ Please submit your own work only (even if it is not working). It is really easy to find out
“similar” programs!
❑ For detailed rules and course policy on plagiarism, please check out
http://myweb.sabanciuniv.edu/gulsend/courses/cs201/plagiarism/
Grade announcements: Grades will be posted in SUCourse, and you will get an Announcement at the
same time. You will find the grading policy and test cases in that announcement.
Grade objections: Since we will grade your homework with a demo session, there will be very likely no
further objection to your grade once determined during the demo.
What and where to submit (IMPORTANT)
Submission guidelines are below. Most parts of the grading process are automatic. Students are expected
to strictly follow these guidelines to have a smooth grading process. If you do not follow these guidelines,
depending on the severity of the problem created during the grading process, 5 or more penalty points are
to be deducted from the grade.
Add your name to the program: It is a good practice to write your name and last name somewhere in the
beginning program (as a comment line of course).
Name your submission file:
❑ Use only English alphabet letters, digits or underscore in the file names. Do not use a blank,
Turkish characters or any other special symbols or characters.
❑ Name your cpp file that contains your program as follows.
“SUCourseUserName_yourLastname_yourName_HWnumber.cpp”
❑ Your SUCourse user name is your SUNet username which is used for checking sabanciuniv
e-mails. Do NOT use any spaces, non-ASCII and Turkish characters in the file name. For
example, if your SUCourse user name is cago, name is Çağlayan, and last name is
Özbugsızkodyazaroğlu, then the file name must be:
cago_ozbugsizkodyazaroglu_caglayan_hw2.cpp
❑ Do not add any other character or phrase to the file name.
❑ Make sure that this file is the latest version of your homework program.
❑ You need to submit ALL .cpp and .h files including the data structure files in addition to your
main.cpp in your project.
Submission:
Submit via SUCourse+ ONLY! You will receive no credits if you submit by other means (e-mail,
paper, etc.).
Successful submission is one of the requirements of the homework. If for some reason, you cannot
successfully submit your homework and we cannot grade it, your grade will be 0.
Good Luck!
Gülşen Demiröz