## 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.

### graph_test

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`.

### hash_test

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:
- Building the tree using the ordinary binary search tree
**treeInsert** will give you a *O(n log n)* running
time, not a *O(n)* running time as requested by the
problem. You will need to construct the tree in a different
manner to get *O(n)*.
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.

- Most people seem to be attacking the problem by figuring out what
the root will be, then its children, etc. It might be more
productive to begin by figuring out what the leaves will be,
and what level they will be at.
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.

- Remember that you have
*O(n)* memory to use. Don't be
shy about using it! With some effort, you can use less, but
we do not ask you to do so.

### 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.