CSC 226
ALGORITHMS AND DATA STRUCTURES II
ASSIGNMENT 2
1. A coin has 1/4 chance of having heads, 3/4 chance of having tails.
a) What is the expected number of coin tosses needed to get a heads? Why?
b) Suppose that such a coin is tossed n times. What is the probability that the number
of heads equals the number of tails? Write the expression using n
x
notation.
2. Draw the hash table resulting from hashing the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16,
and 5, using hash function h(k) = (2k + 5) mod 11, assuming collisions are handled by
each of the following:
a) Separate chaining.
b) Linear probing.
c) Quadratic probing up to the point where the method fails because no empty slot is
found.
d) Double hashing using the secondary hash function h
0
(k) = 7 − (k mod 7).
3. Prove that any connected, undirected graph has a vertex whose removal, along with its
incident edges, will not disconnect the graph by designing a DFS based algorithm to find
such a vertex.
4. Let (x, y, w) denote the edge {x, y} with weight w. The graph for the parts (a)and (b) is
given by nodes V = {A, B, C, D, E} and weighted edges
(A, B, 7),(A, C, 5),(A, D, 1),(B, C, 4),(B, D, 7),(B, E, 1),(C, E, 3),(D, E, 2).
Show how to construct a minimum spanning tree using Prim’s algorithm. List the edges
and nodes in order of when the edge is added to the tree. The first node in T is A. Give
the initial values of D(v) for each node v. Each time a node is added to T, give the D
values which have changed as a result.
5. (a) Show that you can rescale the edge weights of a graph G by adding a positive constant
to all of them without affecting the MST.
(b) Show that Prim’s algorithm still work correctly if the graph G contains edges with
negative edge weights.
