ENS1161_A2_ECU_v10_1_2017.doc
School of Engineering ©ECU 3/02/2017
ENS1161 Computer Fundamentals
ASSIGNMENT 2
Semester 1, 2017
Topics covered: Relations, Functions, Bases and Number Systems, Computer representation of numbers, BCD addition and ASCII codes.
Source material: Lectures 5 to 8 and tutorial exercise sheets on Blackboard.
Marks: 15% of total marks for the unit. The assignment will be marked out of 40 and scaled to a mark out of 15.
Due date: Week 10 of semester (see Blackboard or lecturer for details). A penalty for late submissions will apply as specified in the ECU handbook.
Submission instructions: Please ensure that you submit your assignment in the correct box. (No responsibility will be taken for assignments submitted incorrectly) If you are unsure, check with your lecturer or tutor.
Applications for extension: Applications for extension (on medical or other grounds) should be made in writing to the unit coordinator before the due date, and should be accompanied by appropriate evidence (e.g. medical certificate) to support your application.
Presentation: You may use a computer package to prepare your submission, but it is not essential. In some cases it may be preferable to put in diagrams and symbolic expressions by hand if you are not competent to produce an acceptable result using a computer package. You should use one side of each sheet only. Plastic covers are not required; in fact they usually complicate the processing of submissions.
ENS1161_A2_ECU_v10_1_2017.doc Page 2 of 6
Question 1
Consider the functions f, g and h, all defined on the set {0, 1, 2, 3, …, 12}
x 0 1 2 3 4 5 6 7 8 9 10 11 12 f(x) 5 11 0 9 1 6 10 12 2 8 4 3 7
x 0 1 2 3 4 5 6 7 8 9 10 11 12 g(x) 0 3 7 1 10 12 9 2 11 6 4 8 5
x 0 1 2 3 4 5 6 7 8 9 10 11 12 h(x) 5 4 1 10 8 0 12 9 3 6 2 11 7
(i) Write down the values of: h(g(f(3))) and f –1(h–1(5))
(ii) Construct a table of values (like those shown above) for g(f –1(x)).
(iii) Construct a table for g(g(x)). What can you conclude about the inverse of g?
(iv) Construct a table for h–1(x), and draw its graph on the grid provided on the last page.
[5 marks]
Question 2
Suppose there is a set of growers G = {a, b, c, d}, a set of retailers R = {e, f, g} and a set of customers C = {m, n, p, q, r}. There are two relations A and B on G R and R C, respectively, defined by:
aAe, aAf, bAg, cAf, dAe, and eBn, eBr, fBm, fBq, gBn, gBp
xAy means "grower x sold goods to retailer y", and yA–1x means "retailer y bought goods from grower x"
xBy means "retailer x sold goods to customer y", and yB–1x means "customer y bought goods from retailer x"
(i) Find the matrices M(A) and M(B) that represent the relations A and B.
(ii) Find the matrices M(A)T and M(B)T that represent the relations A–1 and B–1
(iii) Consider the queries:
Which customers have received goods that came from the same grower(s) as those goods received by (a) customer n? (b) customer p?
Find the logical matrix products M(A) M(B) and then M(B)T M(A)T, and finally M(B)T M(A)T M(A) M(B), and hence answer the queries.
[Hint: To see a similar exercise, look at the "Application" on page 13 of Lecture 5.]
[1 + 1 + 3 = 5 marks]
ENS1161_A2_ECU_v10_1_2017.doc Page 3 of 6
Question 3
(a) Consider the following table:
(i) Convert each of the decimal numbers in the first column to octal. (ii) Convert the two octal numbers to binary. (iii) Convert the two binary numbers to hexadecimal. (iv) Add the two hexadecimal numbers. (v) Convert the hexadecimal sum to binary, then to octal and then to decimal. (Give your answers in a table like that above.)
(b) (i) Convert the decimal fraction 0.296875 to binary; (ii) Convert the decimal fraction 0.453125 to binary; (iii) Add the two binary fractions from (i) and (ii); (iv) Convert the binary fraction from (iii) to decimal. (Show your working)
(c) Add the following, given that (i) is binary, (ii) is octal and (iii) is hexadecimal: (i) 1110101 (ii) 2765 (iii) 2FE58 1010111 + 3616 + 1EE4C +
(d) Suppose that the following numbers are all hexadecimal. Carry out the additions with the appropriate "decimal adjustments" so as to obtain answers that are correct when interpreted as decimal. (Show all your working)
(i) 27495 (ii) 156290 33232 + 285612 +
[5 + 2 + 3 + 2 = 12 marks]
Question 4
For each of the following, suppose that two 8-bit binary numbers have been added. In each case the 8-bit output is given and the values of the N, V and C flags. For each case give the correct answer as a decimal number: (a) if the result is interpreted as the sum of unsigned integers; (b) if the result is interpreted as the sum of signed integers.
[10 1 = 10 marks]
decimal octal binary hexadecimal 73 125
8-bit output N V C (i) 0011 1000 0 0 1 (ii) 0100 0110 0 1 1 (iii) 1011 1101 1 0 0 (iv) 1011 1001 1 0 1 (v) 1100 1101 1 1 0
ENS1161_A2_ECU_v10_1_2017.doc Page 4 of 6
Question 5
Introduction – Part 1:
This question refers to "integers mod 5". A brief explanation is given below. If you require more detail, look at the notes for Week 9.
Definition: Two integers a and b are said to be "congruent modulo m" if their difference is a multiple of m; that is if a – b is a multiple of m. If this is so, we write a = b (mod m).
For example:
57 = 27 (mod 10) because 57 – 27 = 30, which is a multiple of 10
44 = 28 (mod 8) because 44 – 28 = 16, which is a multiple of 8
53 = 18 (mod 5) because 53 – 18 = 25, which is a multiple of 5
72 = 30 (mod 6) because 72 – 30 = 42, which is a multiple of 6
33 = 17 (mod 4) because 33 – 17 = 16, which is a multiple of 4
An equivalent way of expressing the same idea is: Two integers a and b are "congruent modulo m" if they leave the same remainder when divided by m.
For example:
57 = 27 (mod 10) because 57 and 27 both leave remainder 7 when divided by 10.
44 = 28 (mod 8) because 44 and 28 both leave remainder 4 when divided by 8.
53 = 18 (mod 5) because 53 and 18 both leave remainder 3 when divided by 5.
72 = 30 (mod 6) because 72 and 30 both leave remainder 0 when divided by 6.
and so on.
Suppose we are working with modulus 5. Since the possible remainders when dividing by 5 are 0, 1, 2, 3 and 4, it follows that every integer must be congruent mod 5 to one of these remainders.
So, for example given an integer such as 693, if we divide by 5 the remainder is 3. Therefore it follows that 693 = 3 (mod 5).
Similarly, by dividing by 5 and keeping the remainders, it follows that:
790 = 0 (mod 5), 841 = 1 (mod 5) and 843 = 3 (mod 5)
These three results are used in the example in Part 2, which follows.
ENS1161_A2_ECU_v10_1_2017.doc Page 5 of 6
Introduction – Part 2:
A data structure called a hash table is useful for any sort of dictionary in which large numbers of words must be stored in a way that allows easy access. The process of hashing allocates words to various groups with a reasonably even distribution of words across the groups.
Suppose, for example, that we are dealing with words up to 10 characters in length, which are to be allocated to 5 groups. Each word is allocated to a group using a hash function h, that is h: {words} {0, 1, 2, 3, 4}, h(word) = some integer (mod 5)
For each word the procedure is: (i) if the word has fewer than 10 characters, then it is padded out with spaces to form a 10-character string; (ii) the ASCII codes of the characters of the 10-character string are added; (iii) the sum of the ASCII codes is reduced to an integer modulo 5;
For example, consider the word petrol: (i) Since the word has only 6 letters, 4 spaces are added to give a 10-character string; (ii) The 8-bit ASCII code for p is 0111 00002, which is 7016 and 11210 Similarly the ASCII code for e is 0110 01012 = 6516 = 10110, and so on. The ASCII code for a space is 0010 00002 = 2016 = 3210 The sum of the ASCII codes is 790 (iii) 790 = 0 (mod 5) Therefore h(petrol) = 0
Similarly h(Sunrise) = 1 and h(Windows) = 3. Notice the different ASCII codes for upper and lower case letters.
Your task:
First work through the above examples in detail to make sure that you understand the process.
Then use the hash function h defined above to find the groups for the four words:
Always snowstorms during February
In other words find the values of h(Always), h(snowstorms), h(during), h(February) Important: Show your working in tables set out as in the examples above.
[2 + 2 + 2 + 2 = 8 marks]
p e t r o l hex 70 65 74 72 6F 6C 20 20 20 20 dec 112 101 116 114 111 108 32 32 32 32 790 0 S u n r i s e hex 53 75 6E 72 69 73 65 20 20 20 dec 83 117 110 114 105 115 101 32 32 32 841 1 W i n d o w s hex 57 69 6E 64 6F 77 73 20 20 20 dec 87 105 110 100 111 119 115 32 32 32 843 3
ENS1161_A2_ECU_v10_1_2017.doc Page 6 of 6
Grid for graph in Question 1
0 12 10 2 4 6 8
2
4
6
8
10
12
0
x
h –1(x)