Below are some hints or suggestions that I hope will make the assignment more approachable and interesting. However, sometimes a hint can confuse more than it helps; if you already have a workable approach to the problems, and the hints don't seem to apply to your approach, don't worry about it.
The format for specifying the graph is described in the documentation for graphRead, in graph_utils.c. A few small and simple graphs are available in ~libsq/usr/lib/asst5/*.grf. You can copy these files to your directory, and then feed them directly to your graph_test program with commands like:
./graph_test < T00y.grfThe files whose names end in ``y.grf'' are connected, while those that end in ``n.grf'' are not (unless I've made some more errors...).
You can test your graph_test on all the test graphs by running the command test_con.
The functions in hash_utils.c will be very useful-- make sure that you read the comments in this file.
The words in the dictionary are not stored in the hash table; the only information stored in the hash table is whether there are any words in the dictionary that hash to each location in the table.
Recall how we solved a similar problem in order to get an $O(n)$ heapify-- some of the same ideas will be useful here.
If you get totally stuck on this part of the problem, a correct O(n log n) algorithm will be worth more points than a bogus O(n) algorithm.
Remember that any complete tree of depth d can be constructed by starting with a perfect tree of depth d-1 and then adding leaves.
The first part can be accomplished by induction.
The second part can be accomplished in several ways-- by induction, or by contradiction (or a combination of the two). The induction is a little trickier to set up, but you have already seen much of one possible proof (disguised as an algorithm) in the reading.