代写data程序课程、代写Java，Python编程语言

日期：2021-10-21 10:44

Question 3 – Hashtables (100 Points)

Question 3. 1 (30/100)

You may use content from Week 7 tutorial (cite when you use) in order to answer this question.

Imagine you are collecting the data for a university. Not to complicate the example, you are collecting

student ID numbers, and corresponding names.

The ID numbers are of the format CCCCCC X, where an X stands for a digit from [0-9] (inclusive), and C stands

for an uppercase letter [A-Z] (inclusive).

Eg: ANERNC 2

Assume that you have a large collection of data, and that you need to look up the names of students with a

given ID number.

1. Create 3 hash functions suitable for the given problem. (Separate the hash function into a hashcode, and a

compression function).

(15 points)

2. Compare and contrast the three hash functions.

(15 points)

Question 3. 2 (70/100)

1. Implement a hashtable with linear probing collission handling. Your hashtable should be able to do

insertions, searches, and deletions.

(30 points)

2. Test your hashtable with “student_records.txt” file given. Report the collission rate for the 3 hash

functions from the section 3.1 above, for 100 names, 200 names, 500 names, the entire dataset.

(30 points)

3. Explain the results from (2) above.

(10 points)

Question 4 – Sorting (100 Points)

Question 4. 1 (30/100)

Consider the 6 sorting algorithms you have learnt: Selection Sort, Insertion Sort, Bubble Sort, Merge

Sort, Heap Sort and Quick Sort. Explain which sorting algorithm(s) is suitable for the three different

scenarios of input data given below. The data is:

1. In random order(i.e., you have no information about the order of the elements)

2. In a nearly sorted order (i.e., only a maximum of 1 or 2 elements are disordered)

3. In reversed order than your expected sorting order (e.g., if your expected order is: 2, 4, 7, 9. 15.

The given data is in the reversed order as 15, 9, 7, 4, 2)

You should provide an explanation for the three different scenarios 1, 2, 3 separately (you may take up

to 150-300 words per scenario.). Your explanation should include, why your chosen sorting algorithm(s)

is suitable for the given scenario over the other sorting algorithms. You may use this tool to compare the

different sorting algorithms you have learnt: https://www.toptal.com/developers/sorting-algorithms

(3 x 10 points)

Question 4. 2 (70/100)

4. Implement the Merge sort algorithm in python to sort a list with “K” elements in the descending

order (decreasing order). You may consider that all “K” elements in the list are integers. You should

write a function “merge_sort” that takes a python list as a parameter and returns a list that is sorted

in the descending order. You are free to write other functions to help with your merge sort

implementation.

Example of the function behavior:

Calling the function: merge_sort([2, 8, 10, 1, 5])

Function output: [10, 8, 5, 2, 1]

(50 points)

5. Answer the following questions based on the Merge Sort algorithm

a. Merge sort belongs to the category of Divide and Conquer algorithm design. Explain the Merge

Sort algorithm with respect to the Divide and Conquer algorithm design paradigm (100 - 250

words)

(10 points)

b. Compare and contrast the Merge sort algorithm with another Divide and Conquer sorting

algorithm you have learnt (100 – 250 words).

(10 points)

Q5 – Graphs (100 Points)

Question 5. 1 (70/100)

Consider a theme park that has “N” number of ride locations. We will consider that 2 <= N <=50 (i.e., the

theme park will have at least 2 rides and can go up to a maximum of 50 rides). The ride locations are

numbered from 1 to N. This theme park only has one-way roads to visit a location of one ride from the

location of another ride. Let’s consider “i” and “j” to be two ride locations in the theme park. Then the

roads between the location of the rides are as follow: for a ride location “i” there is a one-way road from

ride “i” location to ride location “j” if and only if “j == i+1” or “j == i*3”. Also consider that all roads in

this theme park have the same distance.

Your Task

Find the shortest path to visit ride location “N” from ride location 1. Write a python program that will

return the number of roads in the shortest path. Your program should have a callable function with the

naming: “give_me_the_shortest_path” that takes an integer as a parameter and returns an integer

which is the numberof roads in the shortest path that was found. You are free to write other functions

to help your implementation.

Example

Calling the function: give_me_the_shortest_path(6)

Function output: 2

Example Explanation: If we have 6 rides in the theme park based on the above conditions there is a road

from ride location 1 to 2, 1 to 3, 2 to 3, 2 to 6, 3 to 4, 4 to 5 and 5 to 6. Therefore, the shortest path from

ride 1 to 6 is 1 -> 2 -> 6 and the number of roads in this path is 2. Hence the output 2.

Question 5. 2 (30/100)

Answer the following questions based on your solution for Question 5.1.

1. Did you consider any algorithm to solve this problem? If yes, which algorithm did you chose and

why? If no, why? (150- 200 words)

(10 points)

2. If the above problem was changed such that the one-way roads does not have equal distances

(i.e., the distance between two connecting ride locations in the theme park is not the same), can

you use the same algorithm you implemented above? Explain your answer (150-200 words)

(20 points)