Trees and graphs , Theory of Computation

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. 


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


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
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.

Posted Date: 2/14/2013 6:12:01 AM | Location : United States

Related Discussions:- Trees and graphs , Assignment Help, Ask Question on Trees and graphs , Get Answer, Expert's Help, Trees and graphs Discussions

Write discussion on Trees and graphs
Your posts are moderated
Related Questions
These assumptions hold for addition, for instance. Every instance of addition has a unique solution. Each instance is a pair of numbers and the possible solutions include any third

We now add an additional degree of non-determinism and allow transitions that can be taken independent of the input-ε-transitions. Here whenever the automaton is in state 1

proof ogdens lemma .with example i am not able to undestand the meaning of distinguished position .

If the first three words are the boys down,what are the last three words??

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

Define the following concept with an example: a.    Ambiguity in CFG b.    Push-Down Automata c.    Turing Machine

how to convert a grammar into GNF

examples of decidable problems

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

how to understand DFA ?