# Homework 3

Due on Thursday, February 28, 2019 by midnight

(20 Points) Graphs

Consider the undirected graph shown in the following figure. It consists of six nodes A,B,C,D,E,F and ten edges with the shown edge costs.

A 6 C 5 E

1

4

5 2 3 4

B 2 D 4 F

1. (5 Points) Run Dijkstra’s algorithm to find the shortest paths from node A to all other nodes. (Show the final answer and briefly describe the intermediate steps.)

2. (5 Points) Run an algorithm of your choice (e.g., Kruskal, Prim) and find a minimum span- ning tree. (Show the final answer and briefly describe how you got there.)

3. (5 Points) Is the minimum spanning tree of this graph unique? Justify your answer, i.e., if the answer is yes, provide a proof; if the answer is no, provide a counter-example and explain why this is the case.

SPT

4. (5 Points) Consider the average distance from A to all other nodes, first by following edges on the shortest path tree (a), let’s call it davg ; and then following edges on the minimum

MST

spanning tree found in (b), let’s call it davg

SPT

. Which one is greater, davg

or d

avg

MST

? Does

the same answer hold for any graph G = (V, E) and node A V, or is it specific to this

example?

(10 Points) Bellman-Ford Algorithm

Consider the directed graph shown below. The numbers on the edges indicate lengths (or costs) of these edges.

1. (5 Points) Find the shortest paths from all nodes to destination t, using the Bellman-Ford algorithm. Show (some of) your intermediate steps and the final result in the following form: [next hop][distance to t] for every node.

2. (5 Points) After the algorithm reaches steady state, somebody cuts off edges d-t and b- d at the same time. Show the computations following those failures and the new [next hop][distance to t] for every node.

(35 Points) Hashing

The goal is to implement a hash table in C/C++ using open addressing.

## Part A : Hash Table Implementation

• Create your own hash table struct/class that uses open addressing. Do not use any library data structures for implementing your hash tables.
• Use the multiplication method discussed in class for generating your hash function and linear probing to resolve collisions in open addressing.

## Part B : Populating the Hash Table

After constructing the hash table, do the following:

• Generate a random number within the range (0 to 100000).
• Map the generated number to a random integer and insert it into your hash table.
• During insertion, measure the number of times that you have to reprobe the hash table before inserting the value.

Repeat the above operations until your hash table has a load factor of 50% and 90%. Find the average number of reprobes for inserting a random number into the hash table in both cases.

## Part C : Search operation

• Generate a random number within the range (0 to 100000). Do not seed your random number generator.
• Search for the number in your hash table.
• Measure the number of times that you have to reprobe the hash table when it is 50% and 90% full to find the corresponding value.

Repeat the above operations 10000 times and measure the average number of reprobes that have to be performed for a search operation in your hash table.

## Implementation Details

• The hash table must be resizable and its design must be independent of the number of entries inserted into the table.
• Design your hash table in such a way that the number of reprobes is very small.
• If the number of reprobes is large, then modify your hash table design in such a way that the issue is resolved.
• Your submission should contain a Typescript, Makefile and Readme file with instructions to run your program. Failing to include three files, your code will not be graded.

(25 Points) Extra Credit

Implement a hash table using chaining and repeat the above 3 parts for the new hash table.

(35 Points) Prim’s algorithm for MST

The goal is to write a well-structured and well-documented program to implement Prim’s MST algorithm in C/C++.

1. The input graph is to be read in from a file. The format of the file is as follows: The number of vertices, n, is the first line of the file. The vertices are numbered 0, 1, 2, …, n 1. Each subsequent line contains two integers, each between 0 and n 1, indicating the existence of an edge between these two vertices, followed by a number, indicating the weight on the edge. The graph is undirected. For example, a triangle graph in which all the weights are
 0 1 0.1 1 2 0.1 2 0 0.1

0.1 would be represented as follows. 3

2. The output of Prim’s algorithm is a list of edges (and their weights) that constitute a mini- mum spanning tree. Output the MST into a text file.
3. In your implementation of Prim’s algorithm, implement the priority queue with a binary heap.
4. Your submission should contain a Typescript, Makefile and Readme file with instructions to run your program. Failing to include three files, your code will not be graded.
5. Evaluate your code and obtain the running times on the two test graphs – one dense and the other sparse, each with 100000 vertices given to you.

# Submission

When you’ve written up answers to all of the above questions, turn in your write-up and zip/tar- ball of your code by uploading it to Canvas. LATE HOMEWORKS WILL NOT BE ACCEPTED.