Rt3

Theory Assignment #03

Solution: 1) S1-check NODE if NODE= NULL then return true S2-else if NODE! =NULL if LEFT !=NULL and LEFT < NULL then NODE = LEFT repeat step 1 if RIGHT != NULL and RIGHT > NODE then NODE= RIGHT Repeat step1 S3-else : end of if structure Return true S4-exit.

Solution: 2)

Question is incorrect. Given tree is not AVL

Solution: 3)

(a) Graph G

(b) Breadth-first spanning tree of G rooted at b

(c) Depth-first spanning tree of G rooted at c

Solution: 4) As a rough outline, we start with some vertex x, and build a list of the vertices you can get to from x. Each time we find a new vertex to be added to this list, we check its neighbors to see if they should be added as well. Finally, we check whether the list covers the whole graph. In pseudo-code: test-connected(G) { choose a vertex x make a list L of vertices reachable from x, and another list K of vertices to be explored. initially, L = K = x. while K is nonempty find and remove some vertex y in K for each edge (y,z) if (z is not in L) add z to both L and K if L has fewer than n items return disconnected else return connected } To analyze the algorithm, first notice that the outer loop happens n times (once per vertex). The time for the inner loop (finding all unreached neighbors) is more complicated, and depends on the graph representation. One key step (testing whether z is in L) seems like it might be slow, but can be done quickly by keeping a bit on each vertex that says whether it's in L or not.