Description

 

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)
   • 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.
   • 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:

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.

( n < K,

T(n) ≤

n ≥ K.

• 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).
• Using the Big-O notation, give an asymptotic expression for the worst-case running time of KQuickSort. A proof is not required.
• 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.

The vertices are numbered from 1 to n² 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:

<fromVertex> <toVertex> <weight>

In other words, each line after the first corresponds to an edge in the graph and there are as many entries as the number of edges. The edges are bidirectional, i.e. each edge appears twice in the file.

For the example graph pictured above, please see the file maze.txt. The first few lines from this file are:

4

1 2 11

• 5 11
• 1 11
• 3 8
• 2 8

3 4 8

• 7 8
• 3 8
• 1 11

…

Shortest Unweighted Path

For this part, you can ignore the edge weights.

Your task is to determine the shortest path from a source vertex to a target vertex using a breadth first traversal. Source and target vertex pairs will be specified via an input query file that consists of one pair per line. For each pair, please determine the shortest path from the source to the target and use the the supplied MazeVisualizer to visualize the result. If there is no path between a given pair, please indicate that by printing out an appropriate message.

Each line in the input query file has the following format:

<source vertex> <target vertex>

For example, for the source and target vertices 1 and 12 in the figure above, the input line is:

1 12

and the result is pictured below.

Please write a Java program that performs the following tasks:

• Reads the maze information from an input file and uses an appropriate data structure to store this information.
• Reads source and target vertex pairs from an input query file. For each pair, perform a BFS to find the shortest path (ignoring edge weights) from the source to the target. Adjacent vertices should be enqueued in ascending order of vertex number. Alternatively, if you are implementing the bonus portion (see below), your program should implement this using Dijkstra’s algorithm with unit edge weights.
• Visualizes the paths using the supplied MazeVisualizer. MazeVisualizer is a Java applet that provides methods to add edges and paths to be visualized. Multiple paths can be visualized simultaneously. The main method in MazeVisualizer includes relevant calls that demonstrate its use.

Your program will be invoked from the command line as follows: java HW4 maze-file query-file

Please use the supplied maze file and the figure above to test your program. Additional test files and associated output will be made available closer to the due date. Your program should be able to infer the number of vertices in the maze from the maze file. Please do not hard code this information as you will be required to test with larger mazes.

Unlike previous assignments, if you need to make use of auxiliary data structures, please feel free to make use of Java collection classes. The implementation of the shortest path algorithm must be your own. The use of any other code that is not your own is not allowed.

Bonus: Shortest Path using Dijkstra’s Algorithm

Optionally, please implement Dijkstra’s shortest path algorithm to find the shortest weighted path between the source and target vertices supplied in the query file. Visualize these paths using the supplied MazeVisualizer. Your program will be invoked from the command line as follows:

java HW4 [option] maze-file query-file

The command-line argument [option] can take one of two values:

–unweighted: determine the shortest unweighted path. –weighted: determine the shortest weighted path.

To help you test your program, the shortest path using Dijkstra’s algorithm for the pair 1 and 12 (for the example above) is pictured below.

Additional test files and output will be supplied closer to the due date.

If you need to make use of auxiliary data structures, please feel free to make use of Java collection classes. The implementation of Dijkstra’s shortest path algorithm must be your own. The use of any other code that is not your own is not allowed.