Homework #2 Phonebook Solution

Brief descrip+on

In this homework, you are going to implement a phonebook which will help the user to make several opera8ons faster such as searching, adding, dele8ng contacts. For this purpose, you are required to store the contact informa8on in the Binary Search Tree (BST) and AVL tree and experience the implementa8on and performance differences between both data structures. Your tree implementa8ons MUST be template-based.

The Contacts Input File

We will provide you with input files (phonebooks) which are lists of contacts of different sizes where each line is composed of:

firstName lastName phoneNumber city


There is only ONE space between each field. And, each person has only ONE first name and last name.
Therefore, in each line, there are exactly 4 strings. An example input file can be as follows:




















You can assume that the given input file is valid.

The func+onali+es

There has to be 6 available func8ons in your program:

    1. SearchContact

    2. AddContact

    3. DeleteContact

    4. InOrderPrintToFile

    5. PreOrderPrintToFile

    6. DrawTreeToFile
AddContact: Adds a new contact for a given firstName, lastName, phoneNumber and city informa8on to both BST and AVL trees. Note that, while inser8ng into trees, the comparison should be done alphabe8cally.

If the given contact info already exists, print a message to warn the user such as “The given contact full name already exists in the database.” To decide whether a contact info already exists, a full match must be done for the full name. Note that full name is the concatena8on of firstName and lastName by leaving a blank between them. For instance, if firstName is “Ali” and lastName is “Veli”, then the full name will be “Ali Veli”.

DeleteContact: Given the full contact name (firstName+lastName), your program should remove that contact from the phonebook.

SearchAContact: The search should be performed this way:

    • Whenever you enter a full name, your program will display the contact(s) that matches the search full name.

    • If a par8al string is entered, your program should display the contact(s) whose full name starts with the entered par8al word (see sample runs for examples).

InOrderPrintToFile: Print out the phonebook in Pre-order to a file named phonebookInOrder.txt. The informa8on that should be printed is the full name, phone number and city, the same as the input file but ordered as InOrder sorted.

(Debugging hint: the orderings of AVL and BST must be iden8cal).

PreOrderPrintToFile: Print out the phonebook in Pre-order to a file named phonebookPreOrder.txt. The informa8on that should be printed is the full name, phone number and city, the same as the input file but ordered as PreOrder sorted.

DrawTreeToFile: Prints out both BST and AVL (as shown below) into 2 separate files named as phonebookTreeBST.txt and phonebookTreeAVL.txt.


The flow of the program

Once you run your program, it should read the input file (One of the samples given to you, ex: PhoneBook-sample2.txt) and load all its contacts into a BST and an AVL tree. A\er that, your program should display a menu of func8onali8es (func8ons from 1 to 5, given in sample runs) that it should perform successfully. Once a selec8on of a func8on is made, it should be executed for both trees, the BST and the AVL.

Your program will display the execu8on 8mes of each opera8on performed from the list in both trees (The sample runs will explain it thoroughly).

Important: Each node in the tree should contain (Full name, Tel number and City).

Your program should have a list of op8ons to choose which func8on to run on the phone book, the screenshots below show you how your program should look a\er running it.


First, it prompts to ask for an input file which is the phonebook .txt file that will be provided to you. Then, a\er entering the correct file name, the phonebook should be loaded to both, the BST and AVL trees. (Don’t forget to measure tree crea8on 8mes for both trees).






























From this example, you might have no8ced that a\er loading the phonebook to each tree, it prints the heights of both le\ and right subtrees for both BST & AVL trees to show whether the tree is balanced or not. It is IMPORTANT to note that your program must redisplay the same menu a\er running any opera8on in order to perform another one.

Note: The InOrder and PreOrder func8ons should be run using the same choice from the menu (choice

number 4).

Sample runs

Input file: PhoneBook-sample(i).txt

Output files:

    • phonebookInOrderBST.txt

    • phonebookInOrderAVL.txt

    • phonebookPreOrderBST.txt

    • phonebookPreOrderAVL.txt

    • phonebookTreeBST.txt

    • phonebookTreeAVL.txt

Sample Run 1; (PrinLng & Drawing)

Input file: PhoneBook-sample1.txt






















phonebookTreeAVL.txt    phonebookTreeBST.txt

phonebookPreOrder.txt    phonebookInOrder.txt


Hint (Drawing): To draw the tree, you can write a recursive func8on that traverses the tree’s levels. It is pre_y similar to a pre-order prin8ng func8on with few addi8onal code lines where you have to draw something according to whether you are in the le\ subtree or right subtree of each node

Sample Runs 2 & 3

For Sample runs 2 and 3 you can access their files from the sample runs folder (inside homework2 folder) link since the input sizes are much bigger and there is no room for displaying their outputs in the homework document.


























Sample Run 4 (Searching)

Input file: phonk-sample4.txt

An example showing the search opera+on    Another example showing the search

being faster in an AVL than in a BST tree    opera+on being faster in an AVL than in a

BST tree

An example of a par+al string search in both    Searching for key (par+al string) = ‘Gul’


























in

Trees    Sample run 3

Note: for par8al string search in sample run 3, contacts like “Aysegul” or “Mehmet Gul” are not considered in the search result, only “Gulsen Demiroz” and “Gulsah Demirtas” are considered. Important: You should make sure that your code runs on any random input file of any size, therefore, we would probably use other inputs rather than the samples that we have provided you in the homework folder.

Sample Run 5 (DeleLon)

As you will no8ce in the figure below, the dele8on in the AVL tree took less 8me than the dele8on in the BST, it is about 500 8mes faster. However, when the maximum height in the BST is close to the maximum height of the AVL tree, then there will be cases where the dele8on in BST is faster than in AVL.

Please note that you should print a message to indicate that the dele8on “terminated successfully” in case the contact to be deleted exists in the phonebook, otherwise, it should print “Not found”.

Sample Run 6 (InserLon) PhoneBook-sample4.txt

General Rules and Guidelines about Homeworks

The following rules and guidelines will be applicable to all homeworks, 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 clarify 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/in the next page. The submission steps will get natural/easy for later homeworks.




Grading

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 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:

    • We will grade your homeworks during the demo session. Each one of you must show that your code is running as expected and explain several parts of your code if necessary. Wait for an announcement for the demo scheduling.

    • 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 program (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/


Plagiarism will not be tolerated!

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 homeworks 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 in order 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 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 actually 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 VS solution.
        ◦ The name of the main cpp file should be as follows.
“SUCourseUserName_yourLastname_yourName_HWnumber.cpp” For example zubosman_Osmanoglu_Zubeyir_hw3.cpp is a valid name, but hw2_hoz_HasanOz.cpp, HasanOzHoz.cpp are NOT valid names.

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!

Anes Abdennebi, Artun Sarıoğlu and Gülşen Demiröz