Description
This assignment will be marked out of 35 points. You also have an opportunity to earn 5 bonus points. This is an individual assignment. Please review the rules on academic misconduct on the course D2L page. This assignment consists of two parts. The first part consists of problems that will give you more practice working with hash tables and sorting algorithms. The second part consists of a coding exercise that asks you to implement a shortest path algorithm for a graph. You will also get some practice working with multiple source files and Java applets. Part I 1. Hash tables (5 points)
(a) Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is 3/4 and when it is 7/8. Consider all three schemes discussed in class namely: linear probing, quadratic probing, and double hashing. Tabulate your results for comparison. (b) Suppose that in the separate chaining scheme, we also keep the lists in sorted order. With this modification, what is the running time for successful searches, unsuccessful searches, insertions, and deletions? State your answers in terms of the load factor α.
2. (5 points) This question deals with the heapsort algorithm shown below.
function Heapsort(arr) Heapify array arr; for i = n−1 down to 1 do swap arr[i] with arr[0]; restore heap property for the tree arr[0],…,arr[i−1] by percolating down the root; end end
• Identify a suitable loop invariant that will help you show the correctness of heapsort. • Show that your loop invariant holds by showing the initialization and maintenance steps. You can assume that the percolate down operation is correct. • Use your loop invariant to show the partial correctness of heapsort. 3. (7 points) This question deals with the quick sort algorithm.
(a) Suppose that we modify the partitioning algorithm so that it always partitions an input array of length n into two partitions in such a way that the length of the left partition is n−K and the length of the right partition is K −1 (for some constant K, where K 0). Let us refer to this partitioning algorithm as KPartition. Now consider the following variation of quick sort called KQuickSort:
1
CPSC 331: Spring 2018 HW4
function KQuickSort(int[] A, int low, int high) n = high – low + 1; if n < K then insertionSort(A, low, high) ; else q = KPartition(A, low, high) ; KQuickSort (A, low, q-1) ; KQuickSort (A, q+1, high) ; end end Let T(n) denote the worst-case number of steps to run KQuickSort on input arrays of size n. Complete the following recurrence relation for T(n). Assume that KPartition takes Θ(n) steps to partition an array of size n. T(n) ≤( n < K, n ≥ K.
(b) Use the substitution method to find an upper bound on T(n). For simplicity, assume that n is a multiple of K, i.e. n = m·K (where m is a non-negative integer). (c) Using the Big-O notation, give an asymptotic expression for the worst-case running time of KQuickSort. A proof is not required. (d) How does the worst-case asymptotic running time of KQuickSort compare with that of quick sort?
4. (3 points) Prove that a tree with n vertices has n−1 edges. Part II In this coding exercise, you will implement a shortest path algorithm that finds the shortest path between two nodes (if any) in a maze. You can either use a breadth first search (BFS) to find the shortest unweighted path, or (for an added bonus) use Dijkstra’s shortest path algorithm to determine both weighted and unweighted shortest paths. Introduction You are given a maze that is represented as a graph consisting of an n × n grid of vertices. Vertices in the maze are connected via weighted undirected edges to form paths as shown in the figure below.
2
CPSC 331: Spring 2018 HW4
The vertices are numbered from 1 to n2 in a column-major fashion as shown above. The connectivity in the graph is represented in a text file. The first line of this text file consists of the number n and the rest of the lines consist of three integer entries per line in the format:
