Two CSC 326 Homework #1 questions:

> Dear Dr. Frank Ruskey ,
> 
> 
> Could you give me to some idea about the assignment #1?
> 
> 1. about the forest with three nodes,
> 
> let 1 2 3 to represent three nodes, I get four forests
>    a) 1  3   b)  1  2  c)  1   2  d) 1 2 3
>       |          |             |
>       2          3             3
> but the fifth could be the following cases depending on the search
> methods,
> 
>     1          or      1   (preordered)   or   3    (posorder)
>     |                 / \                     / \
>     2                2   3                   1   2
>     |
>     3
> 
> or inorder  2
>           / \
>          1  3
> 
> so what is my probelm?

There are no labels; only the shape of the tree matters.

> 2.the last question is about the dfs
> 
> when I construct the graphic, I have to choose the standard value  for the
> edge to be happened with certain p. my question is how to choose the
> value?
> 
> use the random function provided by the JAVA?
> or I give one ?
> 

Use the Math.random() function from Java and then some test like:
if Math.random() < p then createEdge.

Hope this helps.
Regards,
Frank R.

> Hi Dr. Ruskey,
> 
>   I have a question on the proof of CSC 326 Assignment. After class you
> said
> I should use reduction to proof it, so I will assume we can build the
> Huffman
> Tree in O(n) and based on that I can develop a sorting algorithm with the
> running time O(n). Because there is no sorting algorithm have a running
> time
> O(n) we get the contradiction. That is what I thought after the class. I
> don't
> know if I am on the right track. The problem I have is, I think there is a
> sorting algorithm with running time O(n), the bucket sort. Althought it
> waste
> a lot of memory, but its running time is O(n). So what I should do? Thank
> you
> very much!

Hi XXX,

Lower bounds depend on the computational model.
The computational model for the THETA(n log n) lower
bound on sorting is that the only allowed operations
are comparisons.  You may also assume that it holds
if the items being sorted are integers and that
comparisons and additions are allowed operations
(although formally we would really need to show that
addition does not help).  Bucket sort makes a couple
of assumptions: (a) indexing is allowed, and (b)
the size of the integers is bounded.  Those assumptions
invalidate the THETA(n log n) lower bound.

In terms of the assignment, if you can show that
some PARTICULAR  set of numbers can be "sorted"
in O(n) time IF you had the optimum tree with
those numbers at the leaves, then
that is the crucial part of the question.

-Frank R.

> Hi Dr. Ruskey,
> 
>    I have a question about the ordered forrest in the assignment. Is the 
> following 2 forrests considered to be one or two:
> 
> O  O           O    O
> |                   |
> O        and        O
> 

From the ORDERED forest point of view they are different.
I.e., the ordering of the trees in the forest matters.

>>From the forrest point of view they two are the same, but they do have 
> different left-child right-sibling correspondence.So I am really confused.
> 
> Also about the last question would you mind if we draw the graph by hand?

Sure.