Solutions to other tests:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  

Mathematics for the Digital Age
and
Programming in Python

>>> Second Edition

Test 15

1.
(a), (c), (e)
2.
B
3.
A
4.
A
5.
(a), (c), (d), (e)
6.
(b), (c)
7.
(a), (b), (c)
8.
C
9.
(a) F   (b) T   (c) T   (d) F
10.
(a) T   (b) F   (c) T   (d) T
11.
D
12.
D
13.
C
14.
(a) T   (b) F   (c) T
15.
A
16.
(a) T   (b) T   (c) F   (d) T
17.
D
18.
B
19.
(b), (c)
20.
(c)
21.
(a)

      6

Icosahedron has 12 odd-degree verteces.  At least 6 edges must be removed, one for each pair of vertices, to reduce the degree of each vertex by one, making it even.  Six disjoint edges do exist in the icosahedron.

(b)
22.
def isCycle(V, E): for v in V: if len([e for e in E if v in e]) != 2: return False return True
23.
def distance(E, a, b): r = 0 s = {a} while b not in s: r += 1 s1 = s.copy() for edge in E: if edge[0] in s: s1.add(edge[1]) elif edge[1] in s: s1.add(edge[0]) if len(s1) == len(s): break s = s1 if b in s: return r else: return None
24.
(a)

def toDictionary(V, E): g = {} for v in V: g[v] = set() for e in E: if e[0] == v: g[v].add(e[1]) return g (b)

def toV_E(g): V = set() E = set() for v in g: V.add(v) for v2 in g[v]: E.add((v,v2)) return (V, E)
25.
(a)



(b)

g = {1: {2, 4}, 2: {3, 5}, 3: {5, 6}, 4: {7}, 5: {6, 8, 9}, 6: {9}, 7: {10, 11}, 8: {9, 12, 13}, 9: {13}, 10: {11}, 11: {12}, 12: {13}, 13: set()} (c)

def getSafeUnsafe(g): safe = set() unsafe = set() while len(safe) + len(unsafe) < len(g): for v in g: if g[v].issubset(unsafe): safe.add(v) for v in g: if len(g[v] & safe) > 0: unsafe.add(v) return (safe, unsafe) (d)

from random import choice def getMove(g, safe, v): moves = g[v] if len(moves) == 0: return None if v not in safe: moves = moves & safe return choice(list(moves))
26.
(a)



(b)

g = {'A': {('C', 1), ('E', 2)}, 'B': set(), 'C': {('B', 4), ('D', 3),('F', 1)}, 'D': {('B', 1)}, 'E': {('F', 2), ('G', 1), ('H', 3)}, 'F': {('B', 2), ('H', 2)}, 'G': {('H', 1)}, 'H': set() } (c)

def getOptimalPath(g, a, b): if a == b: return (0, [a]) bestPath = None for edge in g[a]: v = edge[0] w = edge[1] path = getOptimalPath(g, v, b) if (path is not None and (bestPath is None or w + path[0] < bestPath[0])): bestPath = (w + path[0], [a] + path[1]) return bestPath (d)

def getOptimalPath(g, a, b, known = {}): if a == b: return (0, [a]) bestPath = None for edge in g[a]: v = edge[0] w = edge[1] if (v, b) in known: path = known[(v, b)] else: path = getOptimalPath(g, v, b) if (path is not None and (bestPath is None or w + path[0] < bestPath[0])): bestPath = (w + path[0], [a] + path[1]) known[(a, b)] = bestPath return bestPath


Copyright © 2010 by Skylight Publishing