question 2,3,6,14,16
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 correct, 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 your answer for each and every problem. • For free response questions you must clearly justify all conclusions to receive full credit. A correct 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 12 3 36 #13 1 5 5 #14 1 12 12 #15 1 18 18 #16 1 15 15 #17 1 14 14 Total 17 100 1 2Multiple choice problems: For a printed version of the exam, write your answers in the boxes. 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 for 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 response 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¬∃r ( r2 < p−="" q="" )="" .="" a)="" ∃p∃q∃r¬="" (="" r2="">< p−="" q="" )="" b)="" ∃q∃p∃r¬="" (="" r2="" ≥="" p−="" q="" )="" c)="" ∃r∃q¬∃p="" (="" r2="">< p−="" q="" )="" d)="" ∃p∃q¬∃r="" (="" r2="">< p−="" q="" )="" e)="" ∃q∃p∀r="" (="" r2="" ≥="" p−="" q="" )="" f)="" ¬∀p∀q∀r="" (="" r2="">< p− q ) (5) which of the following closed formulas satisfies the recurrence: 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 answer 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 arriving 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 recurrence relation an = 4an−1 − 4an−2 + n. (a) solve for the general solution a (h) n to the associated homogeneous recurrence relation. (b) solve for the particular solution a (p) n to the given recurrence relation: both make the guess and solve for any constants. (c) what is the full general solution to the given recurrence 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 or 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 required 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 currency with p−="" q="" )="" (5)="" which="" of="" the="" following="" closed="" formulas="" satisfies="" the="" recurrence:="" 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="" answer="" 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="" arriving="" 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="" recurrence="" relation="" an="4an−1" −="" 4an−2="" +="" n.="" (a)="" solve="" for="" the="" general="" solution="" a="" (h)="" n="" to="" the="" associated="" homogeneous="" recurrence="" relation.="" (b)="" solve="" for="" the="" particular="" solution="" a="" (p)="" n="" to="" the="" given="" recurrence="" relation:="" both="" make="" the="" guess="" and="" solve="" for="" any="" constants.="" (c)="" what="" is="" the="" full="" general="" solution="" to="" the="" given="" recurrence="" 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="" or="" 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="" required="" 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="" currency="">