CS 503, Advanced Programming I

Quiz 5, 3 April 2007

1. Give an asymptotic worst-case upper bound on the number of edges in an undirected graph with n nodes.

   ---

   Looking at an adjacency-matrix representation of undirected graphs, there can be at most |V|² edges. Because the graph is undirected, there are half as many unique edges. Because there can't be any self-loops, there are |V| less edges for a total of |V|²/2 - |V| edges, which is O(n²).

   ---

2. The dual graph G_D of an undirected graph G is a graph in which every edge in G_D corresponds to a vertex in G and every vertex in G_D corresponds to an edge in G. Explain when the edge (v₁, v₂) would appear in G_D.

   ---

   Two verticies in G_D form an edge if the associated edges in G share a vertex:

   

   ---

3. a) Give the logic-component circuit equivalent to the logical expression

   
   (!C && X && Y) || (C && !X && Y) || (C && X && !Y) || (C && X && Y)
   
   

   b) Describe the program input that would assign all possible combinations of logical values to the circuit's inputs.

   c) Describe the program outputs that should result from the inputs given in b.

   ---

   The program input is

   in0 not0
   in1 and0
   in2 and0
   not0 and0
   in0 and1
   in1 not1
   in2 and1
   not1 and1
   in0 and2
   in1 and2
   in2 not2
   not2 and2
   in0 and3
   in1 and3
   in2 not3
   and0 or0
   and1 or0
   and2 or0
   and3 or0
   or0 out0
   
   0 0 0
   0 0 1
   0 1 0
   0 1 1
   1 0 0
   1 0 1
   1 1 0
   1 1 1
   

   The output should be

   3 0
   3 0
   3 0
   3 1
   3 0
   3 1
   3 1
   3 1
   

   ---

4. A colleague has a graph with a cycle of length 2. Is your colleague's graph directed or undirected? Explain.

   ---

   A cycle of length two is a cycle between two vertices, which has a pair of edges between two vertices. The only way to get two edges between the same two vertices is if they're directed edges pointed in opposite directions:

   

   ---

This page last modified on 8 April 2006.