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

Possibility of recognizing the palindrome language, Computer has a single F... Computer has a single FIFO queue of ?xed precision unsigned integers with the length of the queue unbounded. You can use access methods similar to those in the third model. In this

Computer Simulation, Generate 100 random numbers with the exponential distr... Generate 100 random numbers with the exponential distribution lambda=5.0.What is the probability that the largest of them is less than 1.0?

Chomsky-schutzenberger, The upper string r ∈ Q+ is the sequence of states v... The upper string r ∈ Q+ is the sequence of states visited by the automaton as it scans the lower string w ∈ Σ*. We will refer to this string over Q as the run of A on w. The automa

Context free grammar, A context free grammar G = (N, Σ, P, S)  is in binary... A context free grammar G = (N, Σ, P, S)  is in binary form if for all productions A we have |α| ≤ 2. In addition we say that G is in Chomsky Normaml Form (CNF) if it is in bi

Computation and languages, When we study computability we are studying prob... When we study computability we are studying problems in an abstract sense. For example, addition is the problem of, having been given two numbers, returning a third number that is

Regular languages, LTO was the closure of LT under concatenation and Boolea... LTO was the closure of LT under concatenation and Boolean operations which turned out to be identical to SF, the closure of the ?nite languages under union, concatenation and compl

Production, How useful is production function in production planning? How useful is production function in production planning?

What is chomsky''s classification of grammar, Explain the Chomsky's classif... Explain the Chomsky's classification of grammar

Project, can you plz help with some project ideas relatede to DFA or NFA or... can you plz help with some project ideas relatede to DFA or NFA or anything

Fsa as generators, The SL 2 languages are speci?ed with a set of 2-factors... The SL 2 languages are speci?ed with a set of 2-factors in Σ 2 (plus some factors in {?} Σ and some factors in Σ {?} distinguishing symbols that may occur at the beginning and en