+1-415-670-9189
info@expertsmind.com
Mathematics in computing
Course:- Computer Engineering
Reference No.:- EM13208




Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Computer Engineering

1. The degree(v) of a pendant vertex may be either one or zero. 

     T  or  F 

2. A tree is any connected, undirected graph with an odd number of vertices. 

     T  or  F 

3. A simple graph is an undirected graph with multiple edges but no loops. 

     T  or  F 

4. A multigraph is an undirected graph with multiple edges and no loops. 

     T  or  F 

5. Consider the following directed relations on {1, 2, 3, 4} :

           R = {(1,1), (2,2), (3,3), (4,4)}

           S = {(1,4), (2,3), (3,2), (4,1)}

           R is reflexive and S is symmetric

     T  or  F

6.  Set A is divided into several disjoint partitions.  The UNION of these partitions is the original set.

     T  or  F

7. A W23 has 24 vertices and 46 edges. 

     T  or  F

8. The root of any tree must be at either level 1 (one) or level 0 (zero). 

     T  or  F 

9. A leaf is a vertex with just one child. 

     T  or  F 

10. A weighted graph has a value assigned to each edge. 

     T  or  F 

11. The minimum spanning tree of a weighted graph is a graph that

    is drawn with the length of each edge roughly proportional to

    the value assigned to each edge. 

     T  or  F 

12. Siblings must have the same parent but not necessarily the same level. 

     T  or  F 

13. Since Prim's and Kruskal's algorithms generate the minimum spanning tree of a given weighted graph, each algorithm would always

    provide identical MST solutions. 

     T  or  F 

14. A bipartite graph Kn,m has (n+m) vertices and a maximum of

    (n*m) edges. 

     T  or  F

PART B

1. Form a binary search tree from the words of the following sentence using alphabetical order and inserting words as they appear in the sentence: 

   This test is easier than the last because it is much shorter. 

2. The expression below is in postfix expression form.  Determine its numerical value. 

      { -4,  6,  -,  7,  5,  *,  2,  *,  / }   

3. Determine if Graph Z is bipartite.  Defend your answer.

4. Define a postorder and preorder traversal of the following:

          [(3 - 2y) * 5 ] - [(y - 3) ^ 6) ]  . 

       a. postorder: 

       b. preorder: 

5. Determine the Minimal Spanning Tree in Graph X using Kruskal's

Algorithm.  All edges must be labeled from lower to higher named vertices, e.g., from "c" to "d" but not from "d" to "c".

6. Given the coding scheme:

     a:001, b:0001, e:1, r:0000, s: 0100, t:011, x:01010

   Find the words represented by:  (1 point each)

   a. 0010000011

   b. 001010101

   c. 01110100011

   d. 0001110000

   e. What is the best compression ratio (versus ASCII 8-bit encoding) of the words in a through d above? (2 points).  Defend your answer.

7. Determine the Minimum Spanning Tree in Graph Y. Use Prim's Algorithm in which all edges must be labeled from lower to higher named vertices, e.g., from "c" to "d" but not from "d" to "c"

8. Construct a postorder, inorder and preorder transversal of Tree T.

    a. postorder:  

    b. inorder: 

    c: preorder: 

9. Are Graphs G and H isomorphic?  Defend your answer. 

10. Suppose that a full 41-ary tree has 4 internal vertices.  How many leaves does it have?  Defend your answer.

11. What is the shortest path in Graph S between "a" and "z".  Use Dijkstra's algorithm.

     a. the shortest path is: 

     b. the shortest distance between  "a"  and  "z"  is: 

12. A tree has 37 edges.  How many vertices does it have?

                  EXTRA CREDIT - OPTIONAL

DO ONE of the following: 

A.

Use a greedy algorithm to determine the shortest path in Graph S.  The algorithm starts at vertex "a" and ends at vertex "z" always selecting the shortest edge.  The selection must be in ascending lexicographic order, i.e., m to n  - not n to m.  See discussion on pages 195, 232, and 798.

B.

      Is the solution using Prim's Algorithm in Question B.5 the same topology and length as the required Kruskal solution?

 GRAPH  INFORMATION 

Graph G 

Initially draw a hexagon with vertices a-b-d-f-e-c-a. 

Connect vertices a to f; b to c; d to e. 

        b           d 

 

a                          f 

 

        c           e 

 

Graph H 

Initially draw a hexagon with vertices u-v-w-x-y-z-u. 

Connect vertices u to x; v to y; w to z. 

There is no connection in the center. 

                 u 

 

    z                         v 

 

 

    y                         w

                 x

Graph S 

Initially draw a hexagon with vertices a-b-d-z-e-c-a. 

Connect vertices b to c; b to e; c to d; d to e.

Edge values are: 

  a-b = 3; a-c = 4; 

  b-c = 1; b-d = 5; b-e = 5 

  c-d = 2; c-e = 4; 

  d-e = 1; d-z = 5; e-z = 3. 

 

             b            d 

 

    a                              z 

 

             c            e 

 

Tree T 

Construct a Tree with 

 vertex a at level 0; 

 vertices b, c and d at level 1; 

 vertices e, f, i, j, and k at level 2; 

 vertices g, h, l and m at level 3. 

Connect vertex a to b, a to c, and a to d. 

Connect vertex b to e and f. 

Connect vertex c (no further connection). 

Connect vertex d to i, j and k.

Connect vertex e to g.

Connect vertex f to h.  

Connect vertex i (no further connection).

Connect vertex j (no further connection).

Connect vertex k to l and m.

Connect vertex g, h, l and m (no further connection).

                 a 

 

       b         c         d 

 

    e     f           i    j    k 

 

    g     h                   l   m

 

Graph X 

Initially draw a rectangle with vertices a-c-e-z-d-b-a. 

Connect vertices a to d; c to d; d to e. 

Edge values are:  

  a-b = 1; a-c = 4; a-d =3; 

  b-d = 3; c-d = 3; c-e = 2; 

  d-e = 1; d-z = 2; e-z = 2. 

 

  a         c        e 

 

 

  b         d        z 

 

Graph Y 

Draw a hexagon with vertices a-b-d-z-e-c-a. 

Connect vertices b to c; b to z; d to e. 

Edge values are:

  a-b = 3; a-c = 5;

  b-c = 2; b-d = 5; b-z = 4;

  c-e = 5;

  d-e = 1; d-z = 7; e-z = 3. 

 

             b            d 

 

    a                              z 

 

             c            e 

 

Graph Z

Graph Z is a five-pointed figure.

Connect a to b, a to c and a to e.

Connect b to d.

Connect c to d.

Connect d to e.

 

           b            c

 

   a                             d

 

 

                 e




Put your comment
 
Minimize


Ask Question & Get Answers from Experts
Browse some more (Computer Engineering) Materials
When you input two strings representing your first and last names, have the program output your initials. The program should consist of two files, Initials.java and InitialsA
explain the specifics of the event including date, time, location, charity event, and organization in a 1-2 page flyer. Also, include some sort of history or explanation for
A company's marginal cost function is MC(x)(given below), where x is the number of units. Find the total cost of the first hundred units (x = 0to x = 100).(Round your answer
button is presses if the a disk played is a hit and is not pressed if the disk played is a miss. plan a digital logic system that lights a lamp when a majority of the member
create the product Program to use a GUI. The GUI should display the information one product at a time, including the item number, the name of the product, the number of unit
The university presently uses an analog phone system and the administration is looking to deploy voice over IP solution. Before they move forward, they want to ensure that t
This solution provides the learner with an understanding of two and 3 tierd architectures and explains the role of each architecture. Futher this solution explain the main di
Instructed to develop a LAN for the very successful CPA firm with the five departments within one building and a total of the 560 employees, presently your team can offer.