You may refer to results from previous or subsequent exercises as long as you have no circular references. For instance, you may cite the result of exercise B while proving exercise A, but you could not then cite the result of A to prove B.
Yes, you may use any result from the handouts as long as you reference the source (e.g. handout x, page y).
Yes, an undirected graph is a good way to model this problem, since if A knows B then B knows A.
No, in general if you are given no information as to the directedness of the graph, you should not assume anything one way or the other. It might however not matter. If it matters, you should do a case-by-case analysis. If it doesn't matter, you should explain why.
A full tree is one where every node in the tree (except the leaves which are all at the same level) has m children.
A complete tree is completely filled (see above) except possibly for the lowest level, which is filled from the left up to a point. (The difference is that a full tree is full on all levels, whereas a complete tree may have its final level partially filled.)
A strict m-ary tree means that every node has either 0 or m children.
A tree is ordered not when children are ordered according to some
natural order (numerical, alphabetical, ...) but when there is a
precise and unique left-to-right ordering of the children. For example,
the tree with root "a" and children "b" and "c" could be ordered with
"b" as first or second child. For an unordered tree, the children are
not ordered.
It might help to think of it like this: an
ordered tree has lists of children whereas an unordered tree has
sets.
Note that the ordering starts from the left-most child,
so you cannot have an empty child if you have non-empty children to its
right.
For this problem, we define a "leaf" not as a node with a parent and no children, but simply as a node that has no children. So, a tree consisting of only one node has one leaf and a height of zero.
You need to establish without question why your answer is correct. You do not need to prove unrelated, "obvious" mathematical facts such as 5 > sqrt(5) or that 2x < 3x for positive x. You may cite such facts as sole justification as long as how you used them is clear. You might want to err on the side of caution for the first proof (e.g. explicitly state the definitions and why they support your answer), but subsequent answers may be brief as long as they refer to the same concepts.
The code we refer to is on page 14. Note that line one of "foo" is line (4) of that program.
The result of the modification is:
int foo(int x, int n) {
int i;
for (i = 1; i <= bar(n,n); i++)
x = x + bar(i, n);
return x;
}
Refer to CS103A for the difference between normal and strong induction; e.g. this handout on induction.