Dear guys,

I have looked closer, I have written this, will you please see if the 3
algorithms make any sense, especially 4.3 - and please help with the
running time? Thanks in advance. I need to hand in tonight before midnight.
Thx

4.1

*a.                                           *

       N

P            E

          O       T




*       Change the algorithm Print, such that the recursive flow when
calling Print**(**x**) **for *

*         The root node **x **in the tree from figure 1 prints the colour
sequence ”NETOP” instead of NPEOT.*


Algorithm 3 Print(x)

1: if (*x **≠* NIL) then

2:      print *colour **[**x**]*

3:      if (*right**[**x**]** ≠* NIL) then

4:           *Print(**right**[**x**]**) ** ***

*5:           **Print (**left**[**x**]**)***

6:     end if

7: end if



a.     *Argue for the correctness of your algorithm*: In the algorithm, we
first look at the root and it has a value, then we print N. We then look at
the right child and it has a value, so we print the right values E and T
then we print the left values O and P = NETOP



4.2

*Construct an algorithm **Intern(**x**)**, which, given a root node x for a
tree, returns the number of internal nodes in the tree. *

* *

Algorithm Intern(x)



1: if (x = nil) then

2:      return 0

3: else

4:      return 1 + Intern(left[x]) + Intern(right[x])

5: end if



 *a.     **Give the time complexity/Running time of your solution in **O**
-notation.*



4.3

Construct a recursive algorithm RedRootpath(x), which returns the number 1,
if the tree with the root x has a red rootpath. If such a path does not
exist, the algorithm will return 0.



Algorithm RedRootpath(x)

1: if (x = nil) then

2:      return 0

3: else

4:      if (x=RedRootpath)

5: return 1

6: end if



*a.     **Give the time complexity/Running time of your solution in **O**
-notation. *



On 1 May 2012 12:14, atul anand <atul.87fri...@gmail.com> wrote:

> assignment is not at all tough , i guess you should understand recursion
> to solve these question.
> for eg : in question 4.1 : you just need to swap line number 4 and line
> number 5 to get the solution.
>
> in question 4.2 , you are given code for counting total number of nodes in
> the tree and for counting total number of leaves in the tree.
> soo.... dont you think all information is given and you just need to
> logically think to find the answer . read about what are internal nodes and
> after understanding it see what all question providing you , i hope you can
> get the answer.
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Med Venlig Hilsen/Kind regards

Rose

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Reply via email to