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. 

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.

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
The Myhill-Nerode Theorem provided us with an algorithm for minimizing DFAs. Moreover, the DFA the algorithm produces is unique up to isomorphism: every minimal DFA that recognizes

Question 2 (10 pt): In this question we look at an extension to DFAs. A composable-reset DFA (CR-DFA) is a five-tuple, (Q,S,d,q0,F) where: – Q is the set of states, – S is the alph

i want to do projects for theory of computation subject what topics should be best.

The Last Stop Boutique is having a five-day sale. Each day, starting on Monday, the price will drop 10% of the previous day’s price. For example, if the original price of a product

One of the first issues to resolve, when exploring any mechanism for defining languages is the question of how to go about constructing instances of the mechanism which define part

Exercise:  Give a construction that converts a strictly 2-local automaton for a language L into one that recognizes the language L r . Justify the correctness of your construction.

Suppose A = (Σ, T) is an SL 2 automaton. Sketch an algorithm for recognizing L(A) by, in essence, implementing the automaton. Your algorithm should work with the particular automa

Suppose A = (Q,Σ, T, q 0 , F) is a DFA and that Q = {q 0 , q 1 , . . . , q n-1 } includes n states. Thinking of the automaton in terms of its transition graph, a string x is recogn

The fundamental idea of strictly local languages is that they are speci?ed solely in terms of the blocks of consecutive symbols that occur in a word. We'll start by considering lan

conversion from nfa to dfa 0 | 1 ___________________ p |{q,s}|{q} *q|{r} |{q,r} r |(s) |{p} *s|null |{p}