Homework 4

Homework 4 is out today. Please leave comments here.

Problem 1

Q: .Initially, how are we going to choose C from F while F has no edges? does that mean choosing one node in the first iteration? do we add the minimum edge to F or separate set?

A: if there are no edges in the graph, each node itself is a connected component. In the first iteration, you choose an arbitrary node and then choose  the smallest edge leaving from that node. We will then add the minimum weight edge into F. Suppose the edge we add into F is (u,v).  Now u and v is in the same connected component  And in the second iteration, you can either choose a single vertex w other than (u,v) or you can choose the connected component {u,v}.

The main point of this problem is to show that no matter which connected component is chosen, the algorithm always output the correct Minimum Spanning Tree. Actually, both Prim's algorithm and Kruskal's algorithm can be viewed as a special case of this algorithm when there is a specific way of choosing the connected component.


Problem 2
Q: Can we use hashmap for problem 2a?

A:  You can use hash function.  Please state which hash function you use and what if there are many collisions for the function you choose.

Additional Hint 1.  you can solve the problem WITHOUT using hash function.
Additional Hint 2. there is an algorithm similar to the idea of merge sort.

Q: can you give some more hint on 2b?
Additional Hint: Try to related the problem with the polynomial:  \sum x^d_i


Problem 3
Q: can you give us some hint on Problem 3?

3.1:  run the algorithm for the binary alphabet for k times
3.2:  it is somewhat similar to the algorithm from homework 3's problem 1.
3.3: try to combine the algorithm from the first two problems