SC/MATH 1019B Solutions to Test 3 Nov. 29th 2024
Name:
YorkU email:
Student Number:
READ THE FOLLOWING INSTRUCTIONS.
• Do not open your exam until told to do so.
• No calculators, cell phones or any other electronic devices can be used on this exam.
• Clear your desk of everything excepts pens, pencils and erasers.
• If you need scratch paper, the last page is blank.
• Show all your work unless otherwise indicated. Write your answers clearly!
Include enough steps for the grader to be able to follow your work.
• You will be given exactly 60 minutes for this exam.
I have read and understand the above instructions:
SIGNATUR E
Page 1 of 8
, SC/MATH 1019B Solutions to Test 3 Nov. 29th 2024
Multiple Choice. Circle the best answer. No work needed. No partial credit available.
1. (5 points) Which of are the following relations on {1, 2, 3} is symmetric?
A. {(1, 2), (2, 3), (2, 1), (3, 2)}
B. {(1, 1), (2, 2), (3, 3), (1, 3)}
C. {(1, 2), (2, 3), (3, 1)}
2. (5 points) The graph G = (V, E) where
E = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {2, 4}}
and V = {1, 2, 3, 4} is:
A. a bipartite graph
B. NOT a bipartite graph
3. (5 points) If an is the number of bit strings which do not contain four consecutive 0’s, then an satisfies
which recurrence:
A. an = an−1 + 2an−2 + 3an−3
B. an = an−1 + an−2 + an−3 + an−4
C. an = 2an−1 + 2n−1
D. an = 3an−2 + an−4.
Extra Work Space.
Page 2 of 8
Name:
YorkU email:
Student Number:
READ THE FOLLOWING INSTRUCTIONS.
• Do not open your exam until told to do so.
• No calculators, cell phones or any other electronic devices can be used on this exam.
• Clear your desk of everything excepts pens, pencils and erasers.
• If you need scratch paper, the last page is blank.
• Show all your work unless otherwise indicated. Write your answers clearly!
Include enough steps for the grader to be able to follow your work.
• You will be given exactly 60 minutes for this exam.
I have read and understand the above instructions:
SIGNATUR E
Page 1 of 8
, SC/MATH 1019B Solutions to Test 3 Nov. 29th 2024
Multiple Choice. Circle the best answer. No work needed. No partial credit available.
1. (5 points) Which of are the following relations on {1, 2, 3} is symmetric?
A. {(1, 2), (2, 3), (2, 1), (3, 2)}
B. {(1, 1), (2, 2), (3, 3), (1, 3)}
C. {(1, 2), (2, 3), (3, 1)}
2. (5 points) The graph G = (V, E) where
E = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {2, 4}}
and V = {1, 2, 3, 4} is:
A. a bipartite graph
B. NOT a bipartite graph
3. (5 points) If an is the number of bit strings which do not contain four consecutive 0’s, then an satisfies
which recurrence:
A. an = an−1 + 2an−2 + 3an−3
B. an = an−1 + an−2 + an−3 + an−4
C. an = 2an−1 + 2n−1
D. an = 3an−2 + an−4.
Extra Work Space.
Page 2 of 8
