COMP11120
Two hours
Note that the last two pages contain inference rules for natural deduction
UNIVERSITY OF MANCHESTER
DEPARTMENT OF COMPUTER SCIENCE
Mathematical Techniques for Computer Science
Date: Tuesday 21st January 2020
Time: 14:00 - 16:00
Please answer all THREE Questions
Each question is worth 20 marks
Use a SEPARATE answerbook for each SECTION
© The University of Manchester, 2020
This is a CLOSED book examination
Electronic calculators may be used in accordance with the University regulations
Page 1 of 7 [PTO]
, COMP11120
Section A
1. a) Show that for all natural numbers n it is the case that n is divisible by 4 if and only
if the number given by the last two digits of n is divisible by 4. (4 marks)
b) Consider the following binary operation ~ on the set of binary strings of length
1024. For 0 ≤ i ≤ 1023, the ith symbol in s ~ s0 is
• si if i is even and
• s0i else,
where si denotes the ith symbols in s and s0i denotes the ith symbols in s0 . This
means, for example, if the string s consists exclusively of 0s and the string s0
consists exclusively of 1s then the string s ~ s0 consists of 512 repetitions of 01.
i) Is the given operation commutative? Give a reason for your answer.
(2 marks)
ii) Is this operation associative? Justify your answer. (4 marks)
c) Consider the following function.
f:Z Z
x x + (x mod 3)
Calculate the values of f for inputs from −4 to 3. Is this function injective? Is it
surjective? Justify your answers. (10 marks)
Page 2 of 7
Two hours
Note that the last two pages contain inference rules for natural deduction
UNIVERSITY OF MANCHESTER
DEPARTMENT OF COMPUTER SCIENCE
Mathematical Techniques for Computer Science
Date: Tuesday 21st January 2020
Time: 14:00 - 16:00
Please answer all THREE Questions
Each question is worth 20 marks
Use a SEPARATE answerbook for each SECTION
© The University of Manchester, 2020
This is a CLOSED book examination
Electronic calculators may be used in accordance with the University regulations
Page 1 of 7 [PTO]
, COMP11120
Section A
1. a) Show that for all natural numbers n it is the case that n is divisible by 4 if and only
if the number given by the last two digits of n is divisible by 4. (4 marks)
b) Consider the following binary operation ~ on the set of binary strings of length
1024. For 0 ≤ i ≤ 1023, the ith symbol in s ~ s0 is
• si if i is even and
• s0i else,
where si denotes the ith symbols in s and s0i denotes the ith symbols in s0 . This
means, for example, if the string s consists exclusively of 0s and the string s0
consists exclusively of 1s then the string s ~ s0 consists of 512 repetitions of 01.
i) Is the given operation commutative? Give a reason for your answer.
(2 marks)
ii) Is this operation associative? Justify your answer. (4 marks)
c) Consider the following function.
f:Z Z
x x + (x mod 3)
Calculate the values of f for inputs from −4 to 3. Is this function injective? Is it
surjective? Justify your answers. (10 marks)
Page 2 of 7
