Description
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) |
-
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.
-
Prove whether G has a Euler path or not.
-
Prove whether G has a Euler circuit or not.
-
Prove whether G has a Hamiltonian path or not.
-
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)
-
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)
-
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)
-
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)
-
Carry out a postorder traversal of T and write down the order in which vertices are visited. (1 pt)
-
Carry out an inorder traversal of T and write down the order in which vertices are visited. (1 pt)
-
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)
-
What is the minimum number of vertices in a full ternary (m = 3) tree of height h such that h 2 N+? (1 pt)
-
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)
-
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)
-
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
-
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
-
-
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.
-
-
-
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.
-
-
-
Late Submission: Not allowed
-
-
-
Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
-
-
-
Newsgroup: You must follow the newsgroup (news.ceng.metu.edu.tr) for discussions and possible updates on a daily basis.
-
-
-
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