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)