CISC 4090 Spring 2019 Homework 1 Solutions (100 points total)
Note: according to our book on page 4, the set of natural numbers N does not include 0.
Question 1: (16 points) Examine the following “set-builder” descriptions of the following sets, and provide a list of set members. For full credit your members should show you capture the full diversity and range of the possible elements. Be especially careful for 1c.
Example “builder” description: {y | y=3x and 𝑥 ∈ N} Example answer: {3, 6, 9, 12, … }
Copyright By PowCoder代写 加微信 powcoder
a. {5m|𝑚∈Nandm>5} {30,35,40,…}
b. {𝑥 |𝑥∈Z} {…,-1.5,-1,0.5,0,0.5,1,1.5,…}
c. {w | w is a string over the alphabet consisting of As and Bs, and w is a palindrome (reads the same forward and in reverse)}
{𝜺 , A, B, AA, BB, ABA, BAB, AAA, BBB, ABBA, BAAB, AAAA, …}
d. {(y, y-2) | 𝑦 ∈ N} {(1,-1), (2,0), (3,1), …} Assumes 0 not a natural number
Question 2: (15 points) Provide a “set-builder” description (see Question 1) for each of the sets with elements listed below.
a. {10,100,1000,10000,…}
b. {1,4,7,10,13,…}
c. {3,4,5,6,7,8,…}
d. {1,2,3,4,5,6}
{10x |𝒙∈N}or {10x |𝒙∈Nandx>0} {3x-2|𝒙∈N}𝒐𝒓 {3x-2|𝒙∈Nandx>0}
{x | 𝒙 ∈ N and x>2} {x|𝒙∈Nandx>0andx<7} //x>0optional {x | 𝒙 ∈ N and x>5 and x<2}
Question 3: (20 points)
Let A={ab, aabb, aaabbb, aaaabbbb}, B={ab, abab, ababab}, and C={ab, aabb}
a. 𝐶 ⊆ 𝐴 (circle one)
b. 𝐵 ⊆ 𝐴 (circle one)
c. Whatis𝐵∪𝐶?
d. Whatis𝐴∩𝐵?
e. What is the power set of C?
True False
True False
{ab, abab, ababab, aabb} {ab}
{{}, {ab}, {aabb}, {ab, aabb}}
Question 4: (10 points)
a. Given an arbitrary set A, with a total of |A| elements, how many elements are in the
power set of A?
|P(A)| = 2|A|
b. Given an arbitrary set A and B with |A| and |B| elements respectively, how many elements are in the “Cartesian product” of the two sets-- 𝐴 × 𝐵?
|AxB| = |A| |B|
Question 5: (8 points) Let X be the set {2, 4, 6, 8, 10} and Y be the set {1, 2, 3, 4, 5}. The unary function 𝑓: 𝑋 → 𝑌 and the binary function 𝑔: 𝑋 × 𝑌 → 𝑋 are described in the following tables.
n f(n) 23 43 65 85
a. What is the value of f(8)?
b. What are the range and domain of f?
c. What is the value of g(8,4)?
d. What is the value of f(g(6,5))?
g12345 244444 46661010 6108642 822666
10 4 8 10 8 4
Range: {1, 3, 5} Domain: {2,4,6,8,10} 6
g(6,5)=2, f(2)=3
Question 6: (12 points) Consider the undirected graph G=(V,E) where V, the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1,2}, {1,3}, {2,3}, {3,4}}.
a. Draw the graph G.
b. What are the degrees of each node? Deg(1)=2, Deg(2)=2, Deg(3)=3, Deg(4)=1
c. Write a set of edges forming a path from node 3 to node 4 in the graph.
Question 7: (9 points) Write a formal description of the following graph.
G=(V,E) V={A,B,C,D,E} E={(A,B), (B,C), (B,D), (C,D), (A,D), (D,E)}
Question 8: (10 points) Show that every graph with two or more nodes contains at least two nodes that have equal degrees.
• We do not allow an edge from a node to itself.
• The graph does not have to be connected (some nodes may not have any edges)
Big Hint: Think of the pigeonhole principle, possibly taught in CISC 1100/1400. Feel free to look it up.
Assume there are n nodes, and no nodes have degree 0. The maximum number of degrees allowed is n-1 (one connection to every node that is not yourself). Since there are n nodes and only n-1 different degree options (degree 1, degree 2, ... degree n-1), two nodes MUST have the same number of degrees (n>n-1).
What if degree 0 IS allowed? Let one node have degree 0. The remaining n-1 nodes can have degree 1, degree 2, degree 3, up to degree n-2 (one connection to every node that is not yourself and that is not the node with degree 0 – the node with degree 0 forbids any connections). Because there are n-1 non degree-0 nodes and n-2 options, two nodes MUST have the same number of degrees (n-1>n-2).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com