COSC 214 Data Structures & Algorithms Assignment 3

Instructions for performing the assignment:

Answer (analyze, discuss) the questions clearly, coherently, and professionally.

You are encouraged to read books/online resources. If you get help from these, cite the source in your writing.

o Possible help includes, but is not limited to:

Seeing YouTube video

Seeing the solution to the problem online

Seeing discussions about the problem online

Discussing with someone except your classmates in this course

Submit the assignment on Blackboard. Feel free to contact me (ksarker@bowiestate.edu) anytime for any confusion or difficulty

in understanding.

Grade points and other information:

This assignment has a total of 10 grade points.

Questions 1 to 13 are worth 0.75 points, each totaling 9.75 points.

Overall, clear, coherent, organized writing and submitting the report as

instructed is 0.25 points.

Deliverable:

Submit 1 zip file in Blackboard. o That zip file will include a single PDF file and the source codes for each

problem. PDF file: Analysis, discussion about the problem.

Zip file naming convention - change the bold sections appropriately [ASSIGNMENT-NO]_[STUDENT-NAME].zip

Questions:

1. What is the difference among the following terms - hash function, hashing, and hash map/hash table

a. Give examples and identify the above terms 2. Among direct hashing, linear probing, quadratic probing, and double hashing, which one

do you prefer and why a. How do you design a hash function

i. What factors would you consider in your design 3. Given a table size of 20. Insert the following items using-

- 79, 14, 19, 88, 62, 8, 28, 11, 1, 85, 12, 45, 14, 59, 9, 92, 100, 89, 15, 70 a. Chaining

i. h(x) = x%TableSize b. Linear Probing

i. h(x) = [h(x) + f(i)]%TableSize,

h(x) = x%TableSize

f(i) = i%TableSize, i = 0,1,2,3,4,5...... c. Quadratic Probing

i. h(x) = [h(x) + f(i)]%TableSize,

h(x) = x%TableSize

f(i) = i2%TableSize, i = 0,1,2,3,4,5...... d. Double Hashing

i. h(x) = [h(x) + i * h(x)]%TableSize, i = 0,1,2,3,4,5......

h(x) = x%TableSize

h(x) = Prime_Number - x%Prime_Number

If Student ID ends with an integer value 0, 1, 2, then use

Prime_Number = 17

If Student ID ends with an integer value 3, 4, 5, 6 then use

Prime_Number = 11

If Student ID ends with an integer value 7, 8, 9, then use

Prime_Number = 13

4. What are the differences and similarities among Tree, binary tree, and binary search tree (BST)

a. Give examples

Show the steps of a binary search tree construction for the following integer values

Insert order - 50, 75, 25, 10, 30, 60, 100

Insert order - 100, 75, 60, 50, 30, 25, 10

For each of the constructed binary search trees in question 5

Calculate the height and depth for each node

Categorize the binary tree - full, perfect, complete

Left and right child height difference at each node

Remove the following nodes/items and show the resulting binary tree - a. Remove order - 50, 75

b. Remove order - 75, 30

For a given height, h, what is the maximum and minimum number of nodes?

For a given node number, n, what is the maximum and minimum height of the tree?

What is a Heap, and how it differs from the Binary Search Tree? Give example.

What is the runtime complexity to perform insert and delete (heapify) from the heap

while maintaining heap property?

How can we represent a graph inside computer memory? Give example.

How to traverse a graph? Write the DFS and BFS algorithm's similarities and differences

and give examples.