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 <[email protected]> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
