CS1300_A

Department: Computer Science

Module Code: CS130

Module Title: Mathematics for Computer Scientists I

Exam Paper Code: CS1300_A

Duration: 3 hours

Exam Paper Type: 24-hour window

STUDENT INSTRUCTIONS

1. Read all instructions carefully. We recommend you read through the entire paper at least once before writing.

2. There are 2 questions in Section A and 5 questions in Section B. All candidates should attempt FIVE questions: BOTH from Section A and EXACTLY THREE from Section B. Questions 1 and 2 in Section A are worth 25 and 30 marks, respectively. Each question in Section B is worth 15 marks.

3. You should not submit answers to more than the required number of questions.

4. You should handwrite your answers either with paper and pen or using an electronic device with a stylus (unless you have special arrangements for exams which allow the use of a computer). Start each question on a new page and clearly mark each page with the page number, your student id and the question number. Handwritten notes must be scanned or photographed and all individual solutions collated into a single PDF with pages in the correct order.

5. Please ensure that all your handwritten answers are written legibly, preferably in dark blue or black ink. If you use a pencil ensure that it is not too faint to be captured by a scan or photograph.

6. Please check for legibility before uploading. It is your responsibility to ensure your work can be read.

7. Add your student number to all uploaded files.

8. You are permitted to access module materials, notes, resources, references and the Internet during the online assessment.

9. You must not communicate with any other candidate during the assessment period or seek assistance from anyone else in completing your answers. The Computer Science Department expects the conduct of all students taking this assessment to conform to the stated requirements. Measures will be in operation to check for possible misconduct. These will include the use of similarity detection tools and the right to require live interviews with selected students following the assessment.

10. By starting this assessment, you are declaring yourself fit to undertake it. You are expected to make a reasonable attempt at the assessment by answering the questions in the paper.

IMPORTANT INFORMATION

• We strongly recommend you use Google Chrome or Mozilla Firefox to access the Alter-native Exams Portal.

• You are granted an additional 45 minutes beyond the stated duration of this assessment to allow for downloading/uploading your assessment, your files and any technical delays.

• Students with approved Alternative Exam Arrangements (Reasonable Adjustments) that permit extra time and/or rest breaks will have this time added on to the stated duration.

• You must have completed and uploaded the assessment before the 24-hour assessment window closes.

• Late submissions are not accepted.

• If you are unable to submit your assessment, you must submit Mitigating Circumstances immediately, attaching supporting evidence and your assessment. The Mitigating Cir-cumstances Panel will consider the case and make a recommendation based on the evidence to the Board of Examiners.

SUPPORT DURING THE ASSESSMENT

Operational Support:

– Use the Alternative Exams Portal to seek advice immediately if during the assess-ment period:

∗ you cannot access the online assessment

∗ you believe you have been given access to the wrong online assessment

Technical Support:

– If you experience any technical difficulties with the Alternative Exam Portal please contact [email protected].

– Technical support will be available between 09:00 and 17:00 BST for each exami-nation (excluding Sunday).

Academic Support:

– If you have an academic query, contact the invigilator (using the Contact an Invigi-lator tool in AEP) to raise your issue. Please be aware that two-way communication in AEP is not currently possible.

– Academic support will normally be provided for the duration of the examination (i.e. for a 2 hour exam starting at 09:00 BST, academic support will normally be provided between 09:00 and 11:45 BST). Academic support beyond this time is at the discretion of the department.

Other Support:

– If you can not complete your assessment for the following reasons submit Mitigating Circumstances immediately:

∗ you lose your internet connection

∗ your device fails

∗ you become unwell and are unable to continue

∗ you are affected by circumstances beyond your control

Section A Answer BOTH questions from this section.

1. Find, for each part of the question, an example of a set S and two relations R1 ⊆ S × S and R2 ⊆ S × S such that:

(a) [6 marks] R1 and R2 are partial orders but R1 ∪ R2 is not.

(b) [6 marks] R1 and R2 are equivalence relations but R1 ∪ R2 is not.

(c) [6 marks] R1 and R2 are partial orders and R1 ∩ R2 is an equivalence relation.

(d) [7 marks] each Ri is not reflexive, not symmetric, but transitive, while R1 ∪ R2 = S × S.

2. Answer the following questions, justifying your answers.

(a) [5 marks] For the proposition (x ∨ y) → z to be true, is it necessary that the proposition x ∧ (y ∨ z) is false?

(b) [5 marks] Are the following two propositions logically equivalent?

((((p → q) → r) → s) → t) → p

((((q → r) → s) → t) → p) → q

(c) [5 marks] Express the negation of the sentence

∃z ∀x ∀y ((P(x, z) ∧ P(y, z)) → Q(x, y)) (∗)

so that no negation precedes a quantifier.

(d) [5 marks] What is the truth value of the sentence in Equation (∗) from the previous part, if all variables range over R and the predicates are interpreted as follows:

P(u, v) holds ⇐⇒ u ≥ v,

Q(u, v) holds ⇐⇒ u · v > 0.

(e) [5 marks] Let Q(x, y) be a predicate defined by the following table, where both variables range over the set {1, 2, 3}. Is the sentence ∀y ∃x (Q(x, y) ∧ ¬Q(y, x)) true or false?

(f) [5 marks] Give a predicate R(u, v), where both variables range over the set {a, b}, such that the sentence ∃x ∃y ∀z ¬(R(x, z) → R(y, z)) is true.

Section B Answer EXACTLY THREE questions from this section.

3. Let S = {u, v, w, x, y, z}.

(a) [3 marks] Give an example of an surjective function f : S → {1, 2, 3} or prove that none exists.

(b) [3 marks] Give an example of an injective function f : S → {1, 2, 3} or prove that none exists.

(c) [9 marks] Is it true that, for every injective function f : S → S and for every element e ∈ S there exists an a ∈ S such that f(a) = e ? Justify your answer. Note that, unlike in parts (a) and (b), the co-domain of f is S.

4. Consider the following relation R on the set W = {0, 1} 16. For every two sequences a = (a1, . . . , a16) and b = (b1, . . . , b16) from W, we have R(a, b)    if and only if b = (ak, . . . , a16, a1, . . . , ak−1) for some k ∈ {1, . . . , 16}.

(a) [6 marks] Prove that R is an equivalence relation.

(b) [9 marks] Prove that |W/R| > 1000.

5. [15 marks] Is the set of all undirected simple graphs G that have a proper 4-colouring finite, countably infinite, or uncountable? Justify your answer.

6. [15 marks] Suppose T = (V, E) is a tree with root r ∈ V . Let u and v be two vertices other than r. Let us call u and v rivals if r is the only vertex that lies on some simple path from u to r and on some simple path from v to r.

Is it true that, for all vertices a, b, c other than r, if a and b are rivals but b and c are not, then a and c are rivals too? Justify your answer.

7. [15 marks] Let A, B, C be three events with P[A] = 2/7, P[B] = 1/4, and P[C] = 1/2. If the events A and B are independent, can the inequality P[A ∪ B ∪ C] < 1 be false? Justify your answer.