UNIVERSITY OF VICTORIA EXAMINATIONS APRIL 2018
COMPUTER SCIENCE 226 (A01/A02, CRN 20686/20687)
NAME: V3141592653 INSTRUCTOR: Frank Ruskey .
TO BE ANSWERED ON THE PAPER
REG. NO. I.M. Solution SECTION: A01 DURATION: 3 Hours
STUDENTS MUST COUNT THE NUMBER OF PAGES IN THIS EXAMINATION PAPER BEFORE BEGINNING TO WRITE, AND REPORT ANY DISCREPANCY IMMEDIATELY TO THE INVIGILATOR.
THIS QUESTION PAPER HAS 14 PAGES.
NOTES: (1) ANSWER ALL QUESTIONS, (2) THERE ARE A TOTAL OF 89 MARKS.
Question Possiblemarks 1 26 2 13 38 48 58 6 11 7 15 Total 89
Actualmarks
CSC 226 Page 2 Short Answer Questions:
1. Short answer questions. When running times are asked for, unless otherwise specified, give the answer in the form O(f), where f is the slowest growing function for which the statement is true. For problems involving graphs give your answer in terms of n (the number of vertices), and m (the number of edges). Some of these questions are trivial, some are difficult; leave the difficult ones for later. [26 marks total, 1 for each part]
(a) If a tree has n nodes, then how many edges does it have?
(b) How many key comparisons does it take to merge together two sorted lists, each
Answer: n − 1 Answer: 2n − 1
containing n items?
(c) What is the information theoretic lower bound on the number of comparisons
necessary for sorting n integers? Give an exact expression, not a big-Ω expression. Answer: ⌈lgn!⌉
(d) Finish the theorem statement: A graph is bipartite if and only if
Answer: it has no odd cycles OR chromatic number is 2.
(e) In a red-black tree can there ever be the same number of red edges and black
edges?
Answer: Yes (e.g., one node tree, or tree to right).
(f) In the Edmonds-Karp network flow algorithm what is special about the augment-
ing paths that are used?
Answer: they are shortest (least number of edges).
(g) As a function of m and n, what is the running time of the Edmonds-Karp network flow algorithm?
ANSWER: O(nm2)
(h) Under what condition on the number of vertices can a graph have all vertices of
degree 3 (a so-called cubic graph)?
Answer: |V | must be even (and |V | > 2).
CSC 226
Page 3
(i)
(j)
(k)
(l)
(m)
(n)
(o)
Suppose that you wanted to know routes between Canadian cities that were of the smallest maximum altitude, given a weighted graph of roads (edges) between cities (vertices) and edge weights representing the maximum altitude along each road. What problem studied in this course is most closely related to this problem?
Answer: Minimum spanning tree. What is the greatest number of rotations that can happen in a red-black tree
insertion where the new value is initially inserted at level 4 in the tree?
Answer: 4
What is the equation for the Floyd-Warshall algorithm for solving the all-pairs
shortest path problem?
Answer: d(k) = min{d(k−1), d(k−1) + d(k−1)} ij ij ik kj
Using the Java bit-wise operations, what is (21^42) ?
ANSWER: (111111)2 = 63
In the Bellman-Ford algorithm for finding the shortest path from s to t can it can happen that the shortest path is found on the first pass through the edges. What is the necessary and sufficient condition for this to happen?
Answer: Edges relaxed in the same order that they occur on the shortest path. A binary heap (i.e., as used to implement priority queues) has 1200 nodes. How
many are at the lowest level in the underlying binary tree?
Answer: There are 1023 nodes not at the lowest level, so 1200 − 1023 = 177.
Let T be an extended binary tree with 20 leaves, and suppose that the levels of those leaves (with the root at level 0 as usual) are l1, l2, . . . , l20. What is the value of the following sum?
20
2−li i=1
Answer: Always 1, no matter the leaf count.
CSC 226
(p)
(q)
(r)
(s)
(t)
(u)
(v)
Page 4 A connected planar graph G has 128 faces and every vertex has degree 4. How
many vertices does G have?
Answer: 4-regular implies m = 2n, thus n = 126. What is the maximum number of edges that a 100 vertex planar graph can have?
Assume that the graph is simple; no self-loops and no multiple edges.
Answer: 3·100−6=294
We proved that a simple planar graph G with n vertices and m edges satisfies the bound m ≤ 3n − 6. Now suppose that G is a bipartite graph. What is the stronger bound that we can derive in this case? HINT: a bipartite graph has no triangles.
Answer: Summing a row of Pascal’s triangle, 29 = 512 Simplify the following sum
Answer: m≤2n−4
Simplify the following sum 9 9
k
k=0
9 k=0
(−1)k
9 k
Answer: Always0foranyn>0. Heren=9. A fair coin is flipped 10 times. What is the probability that a total of 4 heads
and 6 tails occur?
Answer: 10/210 = 10/210 46
We say that a binary string has k triples if there are k positions where 3 consec- utive 1s start. For example, 011100111110 has 4 triples. What is the expected number of triples in a random n bit binary string (each bit is independently 0 or 1 with probability 1/2)? HINT: Use linearity of expectation.
Answer: Xk =triplestartsinpositionk,thenE[X1 +X2 +···]=(n−2)/8.
CSC 226
(w)
(x)
(y)
(z)
Page 5 Let (S, T ) be a cut in a flow network. Put in the correct inequality (≤, <, ≥, >)
below.
ANSWER: c(S,T) ≥ f(S,T). The code below comes from an implementation of depth-first-search of a directed
graph with n vertices and m edges as represented using adjacency lists: for (Edge p=adj[v]; p!=null; p=p.next) { … }
In total, over all the various recursive calls, how many times is the test p!=null executed?
ANSWER: true m times, fails n times, so answer is n + m A plane embedding of a connected graph has 100 vertices and 200 edges. How
many faces does it have?
ANSWER: F + V = E + 2, so F = 102. Let T be a rooted tree with the same number of nodes at even levels as there are
at odd levels. Does T necessarily have a perfect matching?
ANSWER: No, lots of small counter-examples.
CSC 226 Page 6
2. [13 marks] Perform a DFS of the graph whose adjacency lists are shown below. Write edges as ordered pairs (v, w) or with arrows v → w. Draw the graph using the style taught in class, clearly indicating the tree edges. Assume that the vertices are pro- cessed in ascending order by the driver program.
Which edges are cross edges? (4,1),(10,3),(10,2),(6,10),(2,9)
Which edges are tree edges? (1,3),(3,9),(3,2),(4,10),(4,5),(5,7),(7,8),(4,6)
Which edges are forward edges? (1,2)
Which edges are back edges? (8,5),(8,4)
List the vertices in the order that they would be output by the book’s topological sorting algorithm (ignore back edges).
ANSWER: 4 6 5 7 8 10 1 3 2 9
1: → 3 → 2
2: → 9
3: → 9 → 2
4: → 1 → 10 → 5 → 6 5: → 7
6: → 10
7: → 8
8: → 4 → 5 9: → 8
10: →3→2
CSC 226 Page 7
3. [8 marks] Below is an internal node in the backtracking tree for the 6 queens problem. (b) Show the next solution that the program discussed in class will discover. Recall that the rows are indexed in increasing order from the bottom.
Q
QQ QQ
QQ QQ
QQ
(a) Use the above configuration to estimate the size of the backtracking tree (i.e., assume that the random experiment ended at the above left configuration).
ANSWER: 1 + 6 + 6 · 3 + 6 · 3 · 2 + 6 · 3 · 2 · 2 + 6 · 3 · 2 · 2 · 1 = 205
(c) On an 6 by 6 board, how many placements of 6 non-taking rooks are there? NOTE: rooks attack along rows and columns, but not diagonals.
ANSWER: 6!
CSC 226 Page 8 4. [8 marks total] The network below corresponds to a bipartite matching problem, one
of the applications we discussed for network flow.
(a) What are the capacities on the edges? [2 marks]
ANSWER: from s and to t, cap = 1, all others are ∞. (b) What are the flow values in the network, given the matched (thickly drawn) edges
shown above? Put the flow values on the edges. [2 marks]
(c) Draw a squiggly line through the edges on a flow-augmenting path from s to t. [4 marks]
You can do your scratch work using the network below.
CSC 226 Page 9 5. [8 marks total]
(a) [2 marks] Recall that rand.nextInt(n) generates a random integer from the set {0, 1, . . . , n − 1}. Fill in the single missing line of code so that the array contains a random permutation of 0, 1, . . . , n − 1 after the second for loop is executed.
for (int i=0; i
int j = rand.nextInt(i+1); <=== ANSWER
int t = a[i]; a[i] = a[j]; a[j] = t;
}
(b) [6 marks] (b) Fill in the missing code below for the book’s implementation of rotation in red-black trees (recall that the book only rotates a red edge and that left, right, N, color are all fields of a Node).
Node rotateRight( Node h ) {
Node x = h.left;
// two assignments to adjust links
h.left = x.right; <=== ANSWER
x.right = h; <=== ANSWER
// two assignments to adjust color
x.color = h.color; <=== ANSWER
h.color = RED; <=== ANSWER
// two assignments to adjust N, the number of descendants
x.N = h.N; <=== ANSWER
h.N = 1 + size( h.left ) + size( h.right ) <=== ANSWER
return x; }
Here, you can assume
int size ( Node x ) { return x==null ? 0 : x.N; }
CSC 226 Page 10
6. [11 marks] Below is a Kattis problem that can be solved with a simple recursive backtracking- like algorithm, efficiently implemented using bitwise operations. Read the problem and turn the page.
Everyone’s favorite character and puppet-maker Geppetto has opened a new pizza place, the best in town. Geppetto is trying to make the best pizza possible, but at the same time he doesn’t want to have a small selection of pizzas.
He makes his pizzas out of N ingredients marked with numbers from 1 to N. All that would be simple if he could mix any ingredient with every ingredient on the pizza, but unfortunately, that is not the case. Sometimes some ingredients cannot mix and that creates additional complications for our pizza master.
There are M pairs of ingredients that cannot be on the same pizza at the same time. Given these restrictions, Geppetto wants to know how many different pizzas he can make. Help him answer this question. Two pizzas are considered different if there is an ingredient of index i that is on one pizza, but not on the other.
Input
The first line of input contains two integers N and M (1 ≤ N ≤ 20, 0 ≤ M ≤ 400). Each of the following M lines contains two different numbers a and b, they represent the prohibition of mixing ingredients marked with a and b on the pizza. (1 ≤ a,b ≤ N). All pairs of ingredients are not necessarily distinct, some pair could occur multiple times.
Output
The first and only line of output must contain the number of different pizzas given the restrictions in the task.
Input 1 Output 1
325 12
23
Input 2 Output 2
308
Input 3 Output 3
334 12
13
23
CSC 226 Page 11
You should read the program below and (a) Write down the 5 different combinations of ingredients corresponding to the first input, (b) determine what E[k] contains after reading all the input, (c) fill in the two underlined blank portions of the program below to make it correct.
(a) [2 marks] ANSWER: ∅, {1}, {2}, {3}, {1, 3}.
Let (a1,b1),(a2,b2),...,(aM,bM) be the set of excluded pairs. Then the j bit of E[k]
is equal to 1 if and only if
(b) [3 marks] ANSWER: There is an excluded pair (j,k) or (k,j).
class Geppetto {
static int[] E = new int[32];
static int count;
static void gen( int k, int A ) {
if (k==0) ++count;
else {
gen( k-1, A );
if (______ (A & E[k]) == 0 _____)
// 3M
} }
gen( k-1, ______ A | 1<
int x = in.nextInt(), y = in.nextInt();
E[x] |= 1<
else { uf[x] = y; sz[y] += sz[x]; }
}
public static void main ( String[] args ) {
Scanner in = new Scanner( new BufferedInputStream(System.in) );
for (int c=in.nextInt(); c>0; –c) {
int N = in.nextInt(); in.nextLine(); // 1 <= N <= 15000
Edge[] E = new Edge[N-1]; // The edges.
in.nextLine();
for (int k=0; k
uf = new int[N]; sz = new int[N];
// Now initialize uf and sz
for(inti=0;i