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. WRITE THE CODE