Assignment 6

Assignment 6#

Dave Friedman
CMPSC 465 Data Structures and Algorithms

1#

For each of the following Horn formulae apply the greedy algorithm discussed in lecture to find a variable assignment that satisfies it, or state that the formula is not satisfiable. Show the complete, step-by-step sequence of assignments made to solve the formula.

A

This set of clauses is not satisfiable.

\( \begin{aligned} (w \land y \land z) &\implies x \\ (x \land z) &\implies w \\ x &\implies y && \text{2. y must be true} \\ &\implies x && \text{1. x must be true} \\ (x \land y) &\implies w && \text{3. w must be true} \\ (\lnot w \lor \lnot x \lor \lnot y) & && \text{not satisfied}\\ \lnot z \\ \end {aligned} \)

\( \begin{array}{c | c | c | c | c} & 0 & 1 & 2 & 3 \\ \hline w & \text{F} & \text{F} & \text{F} & \text{T} \\ x & \text{F} & \text{T} & \text{T} & \text{T} \\ y & \text{F} & \text{F} & \text{T} & \text{T} \\ z & \text{F} & \text{F} & \text{F} & \text{F} \\ \end {array} \)

B

This set of clauses is satisfiable.

\( \begin{aligned} (x \land z) &\implies y \\ z &\implies w && \text{2. w must be true} \\ (y \land z) &\implies x \\ &\implies z && \text{1. z must be true} \\ (\lnot z \lor \lnot x) & \\ (\lnot w \lor \lnot y \lor \lnot z) & \\ \end {aligned} \)

\( \begin{array}{c | c | c | c} & 0 & 1 & 2 \\ \hline w & \text{F} & \text{F} & \text{T} \\ x & \text{F} & \text{F} & \text{F} \\ y & \text{F} & \text{F} & \text{F} \\ z & \text{F} & \text{T} & \text{T} \\ \end {array} \)

C

This set of clauses is not satisfiable.

\( \begin{aligned} &\implies y && \text{1. y must be true} \\ (x \land z) &\implies w \\ (\lnot x \lor \lnot y) & && \text{not satisfied} \\ y &\implies x && \text{2. x must be true} \\ \end {aligned} \)

\( \begin{array}{c | c | c | c} & 0 & 1 & 2 \\ \hline w & \text{F} & \text{F} & \text{F} \\ x & \text{F} & \text{F} & \text{T} \\ y & \text{F} & \text{T} & \text{T} \\ z & \text{F} & \text{F} & \text{F} \\ \end {array} \)

2#

Consider an alphabet \(\Sigma = \{ x, y, z \}\) with the associated symbol frequencies \(f_x, f_y, f_z\) that is Huffman-encoded. For each of the following encodings, state a specific set of frequency values that would result in the stated encodings or explain why the stated encoding could never be attained.

A

\(\{ 1, 01, 11 \}\)

This encoding could never be attained because it is not prefix-free: \(1\) is a prefix of \(11\).

B

\(\{ 1, 01, 00 \}\)

Symbol Frequency
x      4
y      2
z      1

    7
  0/ \1
  3   x
0/ \1
z   y

C

\(\{ 00, 01, 10 \}\)

This encoding could never be attained because its tree representation is not full:

     •
  0/   \1
  •     •
0/ \1 0/ \1
x   y z   •

3#

Consider a cycle within an arbitrary undirected graph \(G\). Prove that if \(e^*\) is the heaviest edge within the cycle and no other edges in the cycle have the same weight \(e^*\) that \(e^*\) will never appear in any valid minimum spanning tree of \(G\).

We know that removing a cycle edge cannot disconnect a graph. Thus removing the heaviest edge within the cycle does not disconnect the graph. Further, an MST by definition minimizes the weight of the tree that preserves the graph’s connectivity. Therefore, there is a connection from one of the “disconnected” components to the other via an edge in the cycle with weight less than \(e^*\) and so \(e^*\) was never part of the MST.

4#

Consider the following weighted undirected graph:

A - (B, 2), (H, 1), (I, 3), (J, 1)
B - (A, 2), (C, 2), (G, 5), (I, 1)
C - (B, 2), (D, 6), (H, 1)
D - (C, 6), (F, 3)
E - (F, 2), (G, 3)
F - (D, 3), (E, 2), (G, 2)
G - (B, 5), (E, 3), (F, 2)
H - (A, 1), (C, 1)
I - (A, 3), (B, 1), (J, 2)
J - (A, 1), (I, 2)

A

Run Kruskal’s algorithm on the graph and state the order in which edges are added to the MST. When a choice must be made between multiple edges always choose the smallest edge in lexicographic order (i.e., the edge with the smallest first vertex, or the smallest second vertex if the first vertex of the two edges is the same).

Order
(A, H, 1)
(A, J, 1)
(B, I, 1)
(C, H, 1)
(A, B, 2)
            (B, C, 2)
(E, F, 2)
(F, G, 2)
            (I, J, 2)
            (A, I, 3)
(D, F, 3)
            (E, G, 3)
(B, G, 5)
            (C, D, 6)

Bitmapped steps
0 0 0 0 0 0 0 0 0    A
1 0 0 0 0 0 0 0 0    B
0 1 0 0 0 0 0 0 0    C
0 0 1 0 0 0 0 0 0    D
0 0 0 1 0 0 0 0 0    E
0 0 0 0 1 0 0 0 0    F
0 0 0 0 0 1 0 0 0    G
0 0 0 0 0 0 1 0 0    H
0 0 0 0 0 0 0 1 0    I
0 0 0 0 0 0 0 0 1    J

0 0 0 0 0 0 1 0 0    AH
1 0 0 0 0 0 0 0 0    B 
0 1 0 0 0 0 0 0 0    C 
0 0 1 0 0 0 0 0 0    D 
0 0 0 1 0 0 0 0 0    E 
0 0 0 0 1 0 0 0 0    F 
0 0 0 0 0 1 0 0 0    G 
0 0 0 0 0 0 0 1 0    I 
0 0 0 0 0 0 0 0 1    J 

0 0 0 0 0 0 1 0 1    AHJ
1 0 0 0 0 0 0 0 0    B  
0 1 0 0 0 0 0 0 0    C  
0 0 1 0 0 0 0 0 0    D  
0 0 0 1 0 0 0 0 0    E  
0 0 0 0 1 0 0 0 0    F  
0 0 0 0 0 1 0 0 0    G  
0 0 0 0 0 0 0 1 0    I  

0 0 0 0 0 0 1 0 1    AHJ
1 0 0 0 0 0 0 1 0    BI 
0 1 0 0 0 0 0 0 0    C  
0 0 1 0 0 0 0 0 0    D  
0 0 0 1 0 0 0 0 0    E  
0 0 0 0 1 0 0 0 0    F  
0 0 0 0 0 1 0 0 0    G  

0 1 0 0 0 0 1 0 1    AHJC
1 0 0 0 0 0 0 1 0    BI  
0 0 1 0 0 0 0 0 0    D   
0 0 0 1 0 0 0 0 0    E   
0 0 0 0 1 0 0 0 0    F   
0 0 0 0 0 1 0 0 0    G   

1 1 0 0 0 0 1 1 1    AHJCBI
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 0 0 0 0 0    E     
0 0 0 0 1 0 0 0 0    F     
0 0 0 0 0 1 0 0 0    G     

1 1 0 0 0 0 1 1 1    AHJCBI
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 1 0 0 0 0    EF    
0 0 0 0 0 1 0 0 0    G     

1 1 0 0 0 0 1 1 1    AHJCBI
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 1 1 0 0 0    EFG   

1 1 0 0 0 0 1 1 1    AHJCBI
0 0 1 1 1 1 0 0 0    DEFG  

1 1 1 1 1 1 1 1 1    AHJCBIDEFG

B

Run Prim’s algorithm on the graph and state the order in which vertices are added to the MST. When a choice must be made between multiple vertices always choose the smallest vertex in lexicographic order.

Order
(A, H, 1)
(A, J, 1)
(B, I, 1)
(C, H, 1)
(A, B, 2)
            (B, C, 2)
(E, F, 2)
(F, G, 2)
            (I, J, 2)
            (A, I, 3)
(D, F, 3)
            (E, G, 3)
(B, G, 5)
            (C, D, 6)

Bitmapped steps
0 0 0 0 0 0 0 0 0    A
0 0 0 0 0 0 1 0 0    AH
0 1 0 0 0 0 1 0 0    AHC
0 1 0 0 0 0 1 0 1    AHCJ
1 1 0 0 0 0 1 0 1    AHCJB
1 1 0 0 0 0 1 1 1    AHCJBI
1 1 0 0 0 1 1 1 1    AHCJBIG
1 1 0 0 1 1 1 1 1    AHCJBIGF
1 1 0 1 1 1 1 1 1    AHCJBIGFE
1 1 1 1 1 1 1 1 1    AHCJBIGFED

5#

Consider the problem of creating an MST for an undirected graph that is not connected (i.e., there are two or more clusters of vertices such that a vertex in one cluster cannot reach a vertex in the other). In this case, we may instead want to construct a minimum spanning forest: a set of MSTs, one for each disconnected component.

Here is the same graph from the previous problem without the two edges (B, G, 5) and (C, D, 6) so that the clusters A B C H I J and D E F G are disconnected from one another.

A - (B, 2), (H, 1), (I, 3), (J, 1)
B - (A, 2), (C, 2), (I, 1)
C - (B, 2), (H, 1)
D - (F, 3)
E - (F, 2), (G, 3)
F - (D, 3), (E, 2), (G, 2)
G - (E, 3), (F, 2)
H - (A, 1), (C, 1)
I - (A, 3), (B, 1), (J, 2)
J - (A, 1), (I, 2)

A

What will happen in this situation if you run Kruskal’s algorithm on the graph? What modifications will be necessary to the algorithm, if any, to achieve the desired goal? Provide a specific example on a disconnected graph of your choosing.

Kruskal’s algorithm will run without issue and generate MSTs for each of the disconnected components. Depending on whether you wanted to return MST values for each conencted component or their sum or average, for example, the algorithm would just require the desired computation as the final step.

Order
(A, H, 1)
(A, J, 1)
(B, I, 1)
(C, H, 1)
(A, B, 2)
            (B, C, 2)
(E, F, 2)
(F, G, 2)
            (I, J, 2)
            (A, I, 3)
(D, F, 3)
            (E, G, 3)

Bitmapped steps
0 0 0 0 0 0 0 0 0    A
1 0 0 0 0 0 0 0 0    B
0 1 0 0 0 0 0 0 0    C
0 0 1 0 0 0 0 0 0    D
0 0 0 1 0 0 0 0 0    E
0 0 0 0 1 0 0 0 0    F
0 0 0 0 0 1 0 0 0    G
0 0 0 0 0 0 1 0 0    H
0 0 0 0 0 0 0 1 0    I
0 0 0 0 0 0 0 0 1    J

0 0 0 0 0 0 1 0 0    AH    1
1 0 0 0 0 0 0 0 0    B 
0 1 0 0 0 0 0 0 0    C 
0 0 1 0 0 0 0 0 0    D 
0 0 0 1 0 0 0 0 0    E 
0 0 0 0 1 0 0 0 0    F 
0 0 0 0 0 1 0 0 0    G 
0 0 0 0 0 0 0 1 0    I 
0 0 0 0 0 0 0 0 1    J 

0 0 0 0 0 0 1 0 1    AHJ   2
1 0 0 0 0 0 0 0 0    B  
0 1 0 0 0 0 0 0 0    C  
0 0 1 0 0 0 0 0 0    D  
0 0 0 1 0 0 0 0 0    E  
0 0 0 0 1 0 0 0 0    F  
0 0 0 0 0 1 0 0 0    G  
0 0 0 0 0 0 0 1 0    I  

0 0 0 0 0 0 1 0 1    AHJ   2
1 0 0 0 0 0 0 1 0    BI    1
0 1 0 0 0 0 0 0 0    C  
0 0 1 0 0 0 0 0 0    D  
0 0 0 1 0 0 0 0 0    E  
0 0 0 0 1 0 0 0 0    F  
0 0 0 0 0 1 0 0 0    G  

0 1 0 0 0 0 1 0 1    AHJC  3
1 0 0 0 0 0 0 1 0    BI    1
0 0 1 0 0 0 0 0 0    D   
0 0 0 1 0 0 0 0 0    E   
0 0 0 0 1 0 0 0 0    F   
0 0 0 0 0 1 0 0 0    G   

1 1 0 0 0 0 1 1 1    AHJCBI    6
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 0 0 0 0 0    E     
0 0 0 0 1 0 0 0 0    F     
0 0 0 0 0 1 0 0 0    G     

1 1 0 0 0 0 1 1 1    AHJCBI    6
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 1 0 0 0 0    EF        2
0 0 0 0 0 1 0 0 0    G     

1 1 0 0 0 0 1 1 1    AHJCBI    6
0 0 1 0 0 0 0 0 0    D     
0 0 0 1 1 1 0 0 0    EFG       4

1 1 0 0 0 0 1 1 1    AHJCBI    6
0 0 1 1 1 1 0 0 0    DEFG      7

B

What will happen in this situation if you run Prim’s algorithm on the graph? What modifications will be necessary to the algorithm, if any, to achieve the desired goal? Provide a specific example on a disconnected graph of your choosing.

Prim’s algorithm will not run properly on a disconnected graph: depending on the starting node, it will generate an MST for the connected component that the starting node is a part of but leave the remainder of the graph unchecked. Prim’s algorithm could undergo a similar modification to that which DFS traversal underwent, a simple iterative component: once there are no more edges to add to the MST set, check to see whether there are unvisited nodes and, if there are, call Prim’s algorithm on one of the unvisited nodes as starting node; and iterate until there are no more unvisited nodes.

Order
(A, H, 1)
(A, J, 1)
(B, I, 1)
(C, H, 1)
(A, B, 2)
            (B, C, 2)
(E, F, 2)
(F, G, 2)
            (I, J, 2)
            (A, I, 3)
(D, F, 3)
            (E, G, 3)

Bitmapped steps
0 0 0 0 0 0 0 0 0    A
0 0 0 0 0 0 1 0 0    AH       1
0 1 0 0 0 0 1 0 0    AHC      2
0 1 0 0 0 0 1 0 1    AHCJ     3
1 1 0 0 0 0 1 0 1    AHCJB    5
1 1 0 0 0 0 1 1 1    AHCJBI   6

0 0 1 0 0 0 0 0 0    D
0 0 1 0 1 0 0 0 0    DF       3
0 0 1 1 1 0 0 0 0    DFE      5
0 0 1 1 1 1 0 0 0    DFEG     7

Assignment 6

Contents

Assignment 6#

1#

2#

3#

4#

5#