Trees and graphs , Theory of Computation

Assignment Help:

Trees and Graphs

Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be sure to include your name and course number within all of the files that you submit. 

1.Trees 

Read the assigned chapter and notes for Week 5 located in the Course Documents area.  

(a)

Draw a binary tree that produces the inorder traversal for the nodes in the following

order: 721, 174, 788, 828, 61, 292, 986, 3, 394, 154, 86, 229. 

Hint: Y

our tree must a binary tree and not a binary search tree. The tree must produce the inorder traversal for the nodes listed in the order provided above. There are several ways that you can draw the tree for this. I recommend first drawing the nodes and links and then filling in the nodes with the correct values that produces the inorder traversal.


 (b)  Briefly explain some of the differences between a multiway tree and a binary search
 
tree.
2. Graphs 
 
Read the assigned chapter and notes for Week 6 located in the Course Documents area.  

(a)  Draw the adjacency list for the following graph:

 

               594_Trees and Graphs.png

 

(b) Briefly state the differences between a sparse and a dense graph, and the mathematical property for each. Also, explain whether a sparse or dense graph is best implemented using and adjacency matrix and why.


Related Discussions:- Trees and graphs

Merging nodes, Another striking aspect of LTk transition graphs is that the...

Another striking aspect of LTk transition graphs is that they are generally extremely ine?cient. All we really care about is whether a path through the graph leads to an accepting

Trees and graphs , Trees and Graphs Overview: The problems for this ...

Trees and Graphs Overview: The problems for this assignment should be written up in a Mircosoft Word document. A scanned hand written file for the diagrams is also fine. Be

Automata and compiler, Automata and Compiler (1) [25 marks] Let N be the...

Automata and Compiler (1) [25 marks] Let N be the last two digits of your student number. Design a finite automaton that accepts the language of strings that end with the last f

Finite-state automaton, Paths leading to regions B, C and E are paths which...

Paths leading to regions B, C and E are paths which have not yet seen aa. Those leading to region B and E end in a, with those leading to E having seen ba and those leading to B no

Equivalence problem, The Equivalence Problem is the question of whether two...

The Equivalence Problem is the question of whether two languages are equal (in the sense of being the same set of strings). An instance is a pair of ?nite speci?cations of regular

Reducibility among problems, A common approach in solving problems is to tr...

A common approach in solving problems is to transform them to different problems, solve the new ones, and derive the solutions for the original problems from those for the new ones

Decidability, examples of decidable problems

examples of decidable problems

Discrete math, Find the Regular Grammar for the following Regular Expressio...

Find the Regular Grammar for the following Regular Expression: a(a+b)*(ab*+ba*)b.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd