CS 202 Fundamental Structures of Computer Science II

Assignment 4 –Balanced Search Trees, Hashing and Graphs

Due Date: July 23, 2010 15:00 (Friday afternoon)

                   You have to give your hard copies before Friday 3:00 pm



Question-1 (25 points)

Starting with an empty balanced-search tree, insert the following keys into the tree in the given order

Keys:  1  6  3  7  5  9  8  4  2

and then delete the keys  5, 9, 1 (in the given order) from the tree.  [On deleting an internal node, a substitute will be chosen from the RIGHT subtree (inorder successor), if needed.]

 

Assume that the balanced-searched tree is implemented as

a)    A 2-3 tree

b)  A 2-3-4 tree

c)  A red-black tree

and show the underlying tree after each insertion and deletion.

 

 

Question-2 (15 points)

Assume that we have a hash table with size 17 (index range is 0..16) and we use mod operator as a hash function to map a given numeric key into this hash table. Draw the hash tables after the insertion of all of the keys 

   11 35 15 25 24 28 2 18

in the given order for each of the following methods.

 

 

Question-3 (10 points)

a)  Give the adjacency matrix and adjacency list representations of the following graph.

 

b) Use both the depth-first strategy and the breath-first strategy to traverse the following graph beginning with vertex 0.

 

 

 

 

 

 

 

 

 

 


Question-4 (50 points) Programming the 2-3-4-Tree

Write a program in C++ language for accepting insertion, deletion, and print requests on a 2-3-4 tree of positive integers from standard input.  Initially, the 2-3-4 tree is empty.  For insertion and deletion, you should use top-down algorithms. On deleting an internal node item, a substitute will be chosen as its inorder successor.

 

Formats:

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 20

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

(null,20,null)

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 10

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

(null,10,null,20,null)

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 5

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

(null,5,null,10,null,20,null)

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 25

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

((null,5,null),10,(null,20,null,25,null))

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 15

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

((null,5,null),10,(null,15,null,20,null,25,null))

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : i 35

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

((null,5,null),10,(null,15,null),20,(null,25,null,35,null))

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : d 5

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : p

((null,10,null,15,null),20,(null,25,null,35,null))

 

Please enter your request (i=insert, d=delete, p=print, e=exit) : e

Bye!

 

 

 

 

Hand-in:

·     You should give the hard copy of your homework that includes the solutions of first three questions during the class hour on the due date. Make sure that your homework must be a printer output with your names, and student ids on them; otherwise it will not be graded.

·     You should also send an email message to your TA, Sefa Kılıç (sefak@cs.bilkent.edu.tr),  attaching with one zipped file (named as  yournameyourlastname.zip ) which contains:

1.       A Word file containing the solutions of first three questions of your homework (hw4.doc) and

2.      Another file (hw4Q4.cpp) containing source code of your C++ program in Question-4.

·         Make sure that the subject field of your email is “CS202 HW4”. You should send this email message before 6:00 pm on the due date. Do not forget to put your name in the header comment in your program.

·         You are free to write your programs in any environment (you may use either Linux or Windows). On the other hand, we will test your programs on “dijkstra.ug.bcc.bilkent.edu.tr” and we will expect your programs to compile and run on the “dijkstra” machine. If we could not get your program properly work on the “dijkstra” machine, you would lose a considerable amount of points. Therefore, we recommend you to make sure that your program compiles and properly works on “dijkstra.ug.bcc.bilkent.edu.tr” before submitting your assignment.

·         Keep all the files before you receive your grade.

 

·         DO IT YOURSELF. CHEATING WILL BE HEAVILY PUNISHED.