CSCI 2824
Final Exam
Remote edition
Spring 2020
Write clearly and in the box:
Name:
Student ID:
Section number:
Read the following:
• RIGHT NOW! Write your name, student ID and section number on the top of your exam. If
you’re handwriting your exam, include this information at the top of the first page!
• You may use the textbook, your notes, lecture materials, and Piazza as recourses. Piazza posts
should not be about exact exam questions, but you may ask for technical clarifications and ask
for help on review/past exam questions that might help you. You may not use external sources
from the internet or collaborate with your peers.
• You may use a calculator.
• If you print a copy of the exam, clearly mark answers to multiple choice questions in the provided
answer box. If you type or hand-write your exam answers, write each problem on their own line,
clearly indicating both the problem number and answer letter.
• Mark only one answer for multiple choice questions. If you think two answers are co
ect, mark the
answer that best answers the question. No justification is required for multiple choice questions.
For handwriting multiple choice answers, clearly mark both the number of the problem and you
answer for each and every problem.
• For free response questions you must clearly justify all conclusions to receive full credit. A co
ect
answer with no supporting work will receive no credit.
• The Exam is due to Gradescope by midnight on Wednesday, May 6.
• When submitting your exam to Gradescope, use their submission tool to mark on which pages
you answered specific questions.
Problems Count Points each Points total
MCQ XXXXXXXXXX
# XXXXXXXXXX
# XXXXXXXXXX
# XXXXXXXXXX
# XXXXXXXXXX
# XXXXXXXXXX
Total 17 100
1
2Multiple choice problems: For a printed version of the exam, write your answers in the
oxes. For typed or hand-written submissions, write each problem on their own line,
clearly indicating both the problem number and answer letter.
(1) Let g(x, y) denote the propositional phrase: ”x loves that new track by y,” where the domain fo
x is all people and the domain for y is also all people (even if they have no flow). Which of the
following quantifiers is logically equivalent to the following English sentence:
“There is a person whose new track is not loved by anybody.”
A) ∀y∀x¬g(x, y)
B) ∃y¬∃x¬g(x, y)
C) ∃x∀y¬g(x, y)
D) ∃y∀xg(x, y)
E) ∃y¬∃xg(x, y)
F) ∃x∀yg(x, y)
G) ¬∃x∀yg(x, y)
(2) Suppose you have the sets A = {1, 2, 3}, B = {a, b, c}, C = {do, re,mi}. What is the cardinality
of the set D = (A ∪B)× (B ∪ C)?
A) 0
B) 3
C) 3 · 2
D) 32
E) 3 · 6
F) 33
G) 62
H) 63
(3) Professor Ella Mint and Dr. M.T. Seht are working together to make a homework where there
are 6 multiple choice questions and 3 free response questions. Every question must be worth at
least one point, and the multiple choice questions must be worth 30 points in total and the free
esponse questions must also be worth 30 points in total. In how many distinct ways can they
allocate points to their 9 questions?
A)
(
60
9
)
B)
(
35
30
)(
33
30
)
C)
(
68
8
)
D) The probability is 1/2, since they either allocate the points or they don’t.
E)
(
30
6
)(
30
3
)
F)
(
29
5
)(
29
2
)
G)
(
9
60
)
(4) Choose the one of the following that is a the logical equivalent of: ∃p∃q¬∃
(
2 < p− q
)
.
A) ∃p∃q∃r¬
(
2 < p− q
)
B) ∃q∃p∃r¬
(
2 ≥ p− q
)
C) ∃r∃q¬∃p
(
2 < p− q
)
D) ∃p∃q¬∃
(
2 < p− q
)
E) ∃q∃p∀
(
2 ≥ p− q
)
F) ¬∀p∀q∀
(
2 < p− q
)
(5) Which of the following closed formulas satisfies the recu
ence:
an = −3an−1 ; a1 = 3
A) an = −3n
B) an = −(−3)n
C) an = n!
D) an = 3n!
E) an = (−3)n
F) an = K
n + L
(
Kn−1
K−1
)
for K = −3 and L = 1
G) an = 3K
n + L
(
Kn−1
K−1
)
for K = −3 and L = 3
H) No closed form solution exists.
(6) Consider the function f(n) = 8 logn(n!) +
√
nn + 6n5/2 − 3n which represents the complexity of
an algorithm. What is the smallest positive integer p such that f(n) is big-O(np)?
A) 0
B) 1
C) 2
D) 3
E) 4
F) There is no smallest such positive integer p.
(7) Determine whether the following argument is valid or invalid and choose the appropriate answe
describing why below: “A CSCI2824 problem is either lame or has jokes. This problem has no
joke. Therefore, it is lame.”
A) This argument is valid; Modus Ponens.
B) This argument is valid; Modus Tollens.
C) This argument is valid; Disjunctive Syllogism.
D) This argument is valid; Hypothetical Syllogism.
E) This argument is invalid; Fallacy of Denying the Hypothesis.
F) This argument is invalid; Fallacy of Affirming the Conclusion.
(8) Suppose we roll 3 fair 6-sided dice and sum their faces. What is the probability that the result is
less than or equal to 5?
A) 0
B) 1216
C) 136
D) 5108
E) 118
F) 7108
G) 16
H) 12
I) 1
Problems 10 and 11 refer to the following set of e-mails and their classifications according to a
Bayesian Spam filter (each column is its own e-mail):
Type: SPAM HAM
puppy kitten reddit humane adopt veterinary discrete
shop food meme puppy kitten spay structures
adorable cbd kitten kitten adorable kitten mudkip
(9) What is the probability that an e-mail contains the word ”kitten”?
(a) 2/3
(b) 5/7
(c) 3/4
(d) 1/7
(e) 1
(f) 0
(g) the number is not listed here
(10) You receive a new message that contains only the word ”kitten.” What is the probability that this
e-mail is SPAM?
(a) 2/5
(b) 3/5
(c) 3/7
(d) 8/7
(e) 1
(f) 0
(g) 1/2
(h) the number is not listed here
(11) We wish to upgrade our Bayesian spam filter to allow for non-independent groupings of multiple
words. Suppose we receive a message that contains the list of words:
[puppies, puppies, puppies, super, cute]
A BSF would then need to compute the probabilities of all possible distinct nonempty subgroups
of words taken from this list. For example, the groups [puppies, puppies], [puppies] are distinct
for this purpose. How many such groups are there?
(a) 3
(b) 7
(c) 8
(d) 15
(e) 16
(f) 31
(g) 32
(12) It’s time for a summer vacation to the almost-deserted island of Knights of Knaves, where there
are only two types of native inhabitants: Knights, who always tell the truth, and Knaves, who
always lie. We need to carefully choose our social distancing circle, so we need to find out who is
who! Upon a
iving at the island, you meet Avi and Boris. Boris tells you that ”Avi is a Knight.”
Avi replies ”Boris and I not of the same type.” What can you conclude?
(a) Avi is Knight and Boris is a Knave.
(b) Avi is Knave and Boris is a Knight.
(c) Both Avi and Boris are Knaves.
(d) Both Avi and Boris are Knights.
(e) You can determine one but not both of their types.
(f) You can not determine either of their types.
Short Answers. If your answers do not fit in the given box, MAKE A NOTE of where the
work is continued or it will NOT be graded!
(13) Consider the following 3 relations:
Relation 1: R1 = {(1, 1), (2, 2), (3, 3), (1, 3), (3, 1), (2, 4), (4, 2)}
Relation 2: R2 ⊆ A×A for the set of people A given by (a, b) ∈ R if and only if a is older than b.
Relation 3: R3 represented by the digraph below
Complete the table below marking with an ”X” in if the given relation is Symmetric (S), Reflexive
(R), or Transitive (T). (Marking ”X” denotes yes or ”It is true that this relation is S/R/T”, not
marking an ”X” denotes no.)
Properties:
S R T
Relations:
R1
R2
R3
(14) Consider the recu
ence relation an = 4an−1 − 4an−2 + n.
(a) Solve for the general solution a
(h)
n to the associated homogeneous recu
ence relation.
(b) Solve for the particular solution a
(p)
n to the given recu
ence relation: both make the guess
and solve for any constants.
(c) What is the full general solution to the given recu
ence relation?
(d) Suppose that for this part of the problem only you are given the initial conditions
a2 = 6 and a3 = 0. Set up but do not solve for the system of equations that would allow
you calculate any remaining unknown constants in your answer to part (c).
Free response problems. If your answers do not fit in one page, MAKE A NOTE of where
the work is continued! Show all work.
(15) The following two questions are unrelated:
(a) Consider the following sentences: ”If it’s a nice day out and also not a Monday, then Zach
will go for a walk.” ”If it’s a Monday, Zach will be tired.” ”Zach is not tired today.” ”It’s a
nice day out.” Is ”Zach will go for a walk” a valid conclusion? Fully justify your argument by
translating all of the above sentences into predicate statements and completing the necessary
proof.
(b) Prove or disprove that if a|bc, where a, b, and c are positive integers with a = 0, then a|b o
a|c.
Additional Workspace
9(16) An undirected graph G = (V,E) is below.
(a) What is the matrix representation of G, with vertices in numerical (ascending) order?
(b) Consider using the Greedy Coloring Algorithm to color G, where the randomly generated
vertex order is [4,3,1,6,7,5,2] and a randomly generated color order is [red, blue, green, purple,
onyx, heather, fuchsia]. What color is the vertex 2 at the end of the algorithm?
(c) Does the graph have an Eulerian tour? Justify your response.
(d) Recall that for a graph G, the chromatic number χ(G) is the minimum number of colors
equired to color the vertices of G. We saw in class that the Greedy Graph Coloring algorithm
does not always find this minimal coloring. Your job is to make a clear argument that zeros
in on χ(G) for the graph above. Can you prove a definite value for χ(G)? If not, can you say
χ(G) is at least some number and at most some number?
Additional Workspace
11(17) In the ancient land of Primea, they use a cu
ency with