Assignment 5 Hints

From the questions I've been getting, it seems like a number of people are having more trouble with this assignment than we anticipated-- this was supposed to be a pleasant wrap-up assignment, not a frustrating experience.

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 question here is ``how do I run the darn thing?'' What graph_test does is reads a graph from standard input, passes the graph it to your graphConnected function (not graphConnect, as incorrectly stated in the assignment), and then it prints a message indicating whether your graphConnected function found that the graph was connected or not.

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.grf
The 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 hash table you are implementing is an array of bits. However, because C does not have an ``array of bits'' type, it is up to you to construct one. The suggested method is to use an array of unsigned integers, where each unsigned int represents BITS_PER_WORD bits.

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.

Building a Complete Tree

Three hints:

Stuffing a DAG With Edges

This problem has two parts: showing that it is possible to cram this many edges into a DAG, and then showing that it impossible to cram any more in.

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.