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:

 

              

 

(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

Ask an Expert

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

Write your message here..

Related Questions

Alphabets - strings and representation, A finite, nonempty ordered set will... A finite, nonempty ordered set will be called an alphabet if its elements are symbols, or characters. A finite sequence of symbols from a given alphabet will be called a string ove

CNF, S-->AAA|B A-->aA|B B-->epsilon S-->AAA|B A-->aA|B B-->epsilon

Finite languages and strictly local languages, Theorem The class of ?nite l... Theorem The class of ?nite languages is a proper subclass of SL. Note that the class of ?nite languages is closed under union and concatenation but SL is not closed under either. N

Myhill-nerode theorem, This close relationship between the SL2 languages an... This close relationship between the SL2 languages and the recognizable languages lets us use some of what we know about SL 2 to discover properties of the recognizable languages.

Path function of a nfa, The path function δ : Q × Σ*→ P(Q) is the extension... The path function δ : Q × Σ*→ P(Q) is the extension of δ to strings: Again, this just says that to ?nd the set of states reachable by a path labeled w from a state q in an

Decision problems of regular languages, We'll close our consideration of re... We'll close our consideration of regular languages by looking at whether (certain) problems about regular languages are algorithmically decidable.

Instantaneous description - recognizable language, De?nition (Instantaneous... De?nition (Instantaneous Description) (for both DFAs and NFAs) An instantaneous description of A = (Q,Σ, δ, q 0 , F) , either a DFA or an NFA, is a pair h q ,w i ∈ Q×Σ*, where

Universality problem, The Universality Problem is the dual of the emptiness... The Universality Problem is the dual of the emptiness problem: is L(A) = Σ∗? It can be solved by minor variations of any one of the algorithms for Emptiness or (with a little le

Regular expressions, The project 2 involves completing and modifying the C+... The project 2 involves completing and modifying the C++ program that evaluates statements of an expression language contained in the Expression Interpreter that interprets fully pa

Programming languages, Different types of applications and numerous program... Different types of applications and numerous programming languages have been developed to make easy the task of writing programs. The assortment of programming languages shows, dif