Homework 05 Solution

Question 1    (15 pts)

Let S be a set of binary strings and R be a relation on S    S, de ned as

S = fw : wis a binary string; jwj    3 ; jn0(w)    n1(w)j    1 ; and wdoes not begin and does not end with 00g

R = f(w1; w2) : w1 2 S ; w2 2 S and w1is a substring of w2g

where jwj denotes the length of the string w, n0(w) and n1(w) are functions that map input strings w to the number of 0's and 1's in w, respectively. Also, use the convention that w1 is a substring of w2 if and only if w1 is contained entirely within w2 for any given strings w1 and w2.

a.
Draw R as a directed graph.
(2 pts)
b.
Prove that (S; R) is a poset.
(4 pts)
c.
Is (S; R) a total order? Prove your answer.
(3 pts)
d.
Draw a Hasse diagram for (S; R). State the maximal and minimal elements.
(4 pts)
e.
Identify whether (S; R) constitutes a lattice or not.
(2 pts)

Question 2    (24 pts)

Given the directed graph G in Figure 1, answer the questions.



a    e




b




d  c    f  g



Figure 1: Graph G in Q2.

a. Provide an adjacency list representation of G.
(3 pts)
b. Provide an adjaceny matrix representation of G.
(3 pts)
c. Compute indegrees and outdegrees of every vertex in V .
(3 pts)
d. List 6 di erent simple paths of length 4 in G.
(3 pts)
e. List all simple circuits of length 3 in G.
(3 pts)
f. Prove that G is weakly-connected.
(3 pts)
g. Identify strongly-connected components of G.
(3 pts)

    h. How many di erent paths of length 3 exist between every distinct pairs of vertices in the subgraph

H of G induced by the vertices fa; b; c; dg    V ?    (3 pts)


Question 3    (16 pts)

Given the undirected graph G in Figure 2, answer the following questions using clear formalism.




a    b    c    d




e    f




 h    i     j

Figure 2: Graph G in Q3.

    a. Prove whether G has a Euler path or not.

    b. Prove whether G has a Euler circuit or not.

    c. Prove whether G has a Hamiltonian path or not.

    d. Prove whether G has a Hamiltonian circuit or not.




g




k




(4 pts)

(4 pts)

(4 pts)

(4 pts)

Question 4    (10 pts)

Let Km;n denote a complete bipartite graph such that exactly m and n vertices exist in its two disjoints sets of vertices such that m ; n 2 N+, respectively.
a. How many vertices and edges does Km;n have?    (3 pts)

b. Prove that Km;n with odd m and even n does not have a Hamiltonian circuit.    (7 pts)



























2

Question 5    (20 pts)

Given the undirected graph G in Figure 3, answer the questions.


u

11

y






4

8

6
9




1

1   s
5
v
2
x  4
t






3

3
8
6
3








w    z
12

Figure 3: Graph G in Q5.

a. Find the shortest path from s to t using Dijkstra's algorithm. Clearly show each step.    (7 pts)

    b. Find a minimum spanning tree with root as vertex x using Prim's algorithm in Section 11.5 of the

textbook. Explicitly show every step of computation.    (5 pts)

    c. Following edges are added to G one-by-one in order:

(s; x; 1) (t; u; 6)
(s; z;    3)

(u; y; 3)

(w; z;    1).

Without ever calling Prim's algorithm (or any other algorithm computing minimum spanning trees for graphs from scratch), modify the minimum spanning tree you generated in b so that it maintains to be a minimum spanning tree after the rst weighted edge is added to G. Repeat this for the re-maining edges, each time modifying the previously constructed minimum spanning tree. Separately
draw minimum spanning trees of G for each new edge in given order.    (5 pts)

    d. Do you think you can iteratively update the shortest path from s to t without calling Dijkstra's

algorithm upon the arrival of listed edges in c? Justify your answer.    (3 pts)

Question 6    (15 pts)

Answer options a-f using the binary tree T in Figure 4. Vertices of T are marked with <identifier:key> annotations. Note that T has the vertex p as its root. Use the notational conventions in your textbook to decide whether a vertex is left or right child of some vertex whenever applicable.











3

p:42





q:34    r:75





s:26    t:37    u:63    v:98





w:33    m:35    x:41    y:71    z:99





n:61


Figure 4: Tree T in Q6 options a, b, c, d, e, f.

a. What are the number of vertices, the number of edges and the height of T ?    (1 pt)

    b. Carry out a postorder traversal of T and write down the order in which vertices are visited. (1 pt)

    c. Carry out an inorder traversal of T and write down the order in which vertices are visited.  (1 pt)

    d. Carry out a preorder traversal of T and write down the order in which vertices are visited.  (1 pt)

e. Is T a full binary tree? Justify your answer.    (1 pt)

f. Is T a binary search tree using provided keys under comparison with respect to the    relation

de ned on Z    Z? Justify your answer.    (1 pt)

    g. What is the minimum number of vertices in a full ternary (m = 3) tree of height h such that h 2 N+? (1 pt)

    h. Construct a binary search tree of minimum height for the following set of integer keys f9; 3; 11; 15; 1; 7; 22; 21
employing the    relation de ned on Z    Z.    (2 pts)

    i. Using the binary search tree in h, give sequences of vertices that are probed in order to  nd vertices

with key values 2 and 22, repsectively.    (1 pt)

j. Construct a binary search tree of maximum height for the following set of binary string keys f001; 1; 10; 010; 0000g using lexicographic ordering (how strings would be listed in a dictionary
assuming that 0 comes before 1 in the alphabet) for comparison.    (2 pts)

    k. Using the binary search tree in j, give sequences of vertices that are probed so as to  nd vertices

with key values 001 and 011, respectively.    (1 pt)


4

    l. Construct a spanning forest for the directed graph G in Figure 1 via breadth- rst search under the assumption that unvisited vertices are selected for expansion in reverse alphabetic order of vertex

identi ers.    (2 pts)

    • Regulations

        1. You have to write your answers to the provided sections of the template answer le given. Other than that, you cannot change the provided template answer le. If a latex structure you want to use cannot be compiled with the included packages in the template le, that means you should not use it.

        2. Do not write any other stu , e.g. question de nitions, to answers’ sections. Only write your answers. Otherwise, you will get 0 from that question.

        3. Late Submission: Not allowed

        4. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.

        5. Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.

        6. Evaluation: Your latex  le will be converted to pdf and evaluated by course assistants.  The

.tex le will be checked for plagiarism automatically using "black-box" technique and manually by assistants, so make sure to obey the speci cations.

    • Submission

Submission will be done via COW. Download the given template le, \hw5.tex", when you nish your exam upload the .tex le with the same name to COW.

Note: You cannot submit any other les. Don’t forget to make sure your .tex le is successfully compiled in Inek machines using the command below.

$ pdflatex hw5.tex




























5