Assessment 1 Model Answer

This is the model answer for Assessment 1. Multiple methods have been provided for answering some questions. There may be other valid methods for getting to the correct answer.

In marking the assessment, partial marks are given for working, and for error carried forward (ECF), where an answer is correct but for an incorrect value brought forward from an earlier question for which the student has already lost marks.

A demo of the model answer code is available on Replit. The test code that was used in marking the assessments is available on GitHub for Java and for Python.

Part 1: Number Theory [ 35 marks ]

Numerical Systems [ 18 marks ]

  1. What is the result of \( 00111011 - 10101010 \)`? Assume numbers are stored with 8 bits. You must show your working to get the mark. [ 1 mark ]

    First we find the twos-compliment of the second number:

    We flip each bit of 10101010 to get the one’s compliment and add 1.

     01010101 (= one's compliment)
 00000001 +
 --------
 01010110 (= two's compliment)

    Now we do binary addition using the twos compliment:

     00111011
 01010110 +
 --------
 10010001

  2. What is the result of \(10101010 \times 101 \)? You must show your working to get the mark. [ 1 mark ]

    We can use binary multiplication to find the answer:

       10101010
        101 *
   --------
   10101010
  000000000     
 1010101000 +
 ----------
 1101010010

  3. What is the remainder and quotient when you divide of \( 111010 \div 101 \)`? You must show your working to get the mark. [ 2 marks ]

    We can use binary division to find the answer:

             1011
     ---------
 101 | 111010
       101
       -------
        10010
         101
         -----
         1000
          101
          ----
          011

    quotient: 1011

    remainder: 11

  4. Implement the following methods in a programming language. You must not make use of built-in methods, such as Integer.parseInt() to parse the Strings. You must not represent the binary values as numerical data types such as int. [ 6 marks ] 
     /**
 * This function accepts two binary strings (Strings containing only the
 * characters '0' and '1') and returns the result of binary addition.
 * @param a - The first binary number
 * @param b - The second binary number
 * @return A String representing the binary sum of the two arguments.
 **/
 static String binaryAddition(String a, String b)
 {
     String out = "";
     int len = Math.max(a.length(), b.length());
     boolean carry = false;
     for (int i = 1; i <= len; i++)
     {
         boolean aVal = ((i <= a.length()) && (a.charAt(a.length()-i) == '1'));
         boolean bVal = ((i <= b.length()) && (b.charAt(b.length()-i) == '1'));

         if (aVal && bVal)
         {
             out = (carry ? "1" : "0") + out;
             carry = true;   
         }
         else if (!aVal && !bVal)
         {
             out = (carry ? "1" : "0") + out;
             carry = false;
         }
         else
             out = (carry ? "0" : "1") + out;
     }
     return out;
 }

 /**
 * This function accepts two binary strings (Strings containing only the
 * characters '0' and '1') and returns the result of binary multiplication
 * of the binary numbers.
 * @param a - The first binary number
 * @param b - The second binary number
 * @return A String representing the binary sum of the two arguments.
 **/
 static String binaryMultiplication(String a, String b)
 {
     String bin = "0";  
     for (int i = b.length()-1; i >= 0; i--)
     {
         if (b.charAt(i) == '1')
             bin = binaryAddition(bin, a);
         a = a + "0";
     }
     return bin;
 }

  5. What is the base 4 number 132 in hexadecimal? You must show your working to get the mark. [ 1 mark ]

    A hexadecimal digit is represented by 4 base 2 (binary) digits (\(2^4 = 16 \)). It is represented as 2 base 4 digits (\( 4^2 = 16 \)). Therefore we convert each pair of base-4 digits to one hex digit.

    We start pairing from the right, and pad the left with zeroes if necessary. The pairs are: \( 01 \), \( 32\) . The first number in each pair is in 4s = \( 4^1 \), the second is in 1s (units) = \( 4^0 \)

    \( 3 \times 4^1 + 2 \times 4^0 = 14 = E_{16}\)

    \( 0 \times 4^1 + 1 \times 4^0 = 1 = 1_{16}\)

    \( 0132_4 = 1E_{16} \)

Unix File Permissions

Unix file permissions look like this rwx-rw-r--. They consist of 9 binary flags in groups of 3. The first group corresponds to user permissions, the second to group permissions, the third to everyone else. Each group has three flags, written with the characters r, w, and x corresponding to read (r), write (w) execute (x).

Permissions for a file may look like: rw-r--r--, meaning the user can read and write it, the group can read it, and everone else can read it. This is also expressed as the octal number 611.

A file where everyone can read, write and execute it would have the string rwxrwxrwx. This is also expressed as the octal number 777.

Some example file permissions and equivalent numbers are given below.

  • r---w---x = 421
  • -w---xr-- = 214
  • rw-rw-rw- = 555
  • --------- = 0
  • --------x = 1
  • -----x--- = 10
  • --x------ = 100
  • rwxrwxrwx = 777
  1. Implement the following methods in a programming language. You may make use of built-in methods, such as Integer.parseInt() to parse the Strings. You may represent the binary values as numerical data types such as int. [ 3 marks ][4 marks ]
/** 
* Convert unix file permissions string to number
* @param permissions - unix file permissions string such as `rw-rw-r--`
* @return A string containing the number expressed in octal
**/ 
static int filePermissionsToNumber(String permissions)
{
    int out = 0;  
    for (int i = 0; i < 3; i++)
    {
        int num = 1;  
        for (int j = 2; j >= 0; j--)
        {
            if (permissions.charAt((i*3)+j) != '-')
                out += num * Math.pow(10,2-i);
            num *= 2;
        }
    }
    return out;
}

/** 
* Convert number into a unix file permissions string
* @param num - number to convert, such as 664
* @return Unix file permissions string such as `rw-rw-r--`
**/ 
static String numberToFilePermissions(int num)
{
    int d3 = num % 10;
    int d2 = (num/10) % 10;
    int d1 = (num/100) % 10;

    return toFileBinary(d1) + toFileBinary(d2) + toFileBinary(d3);
}

static String toFileBinary(int number)
{
    String c = "rwx";
    String output = "";
    int i = 2;
    do {
        if (number % 2 == 1)
            output = c.charAt(i) + output;
        else
            output = "-" + output;
        i--;
        number /= 2;
    } while (output.length() < 3);

    return output;
}

Modular Arithmetic [ 8 marks ]

  1. Give a value of \( a \) such that: \( (4 + 2) \bmod a \times 10 \bmod a - 5 \bmod a \equiv 0 \pmod{a} \) [ 1 mark ]

    2. Multiple answers are possible here:

    \( a = 1 \), \( a = 5 \), \( a = 11 \), \( a = 55 \)

  2. What is \( 4^{-1} \pmod{19}\)? [ 1 mark ]

    3. The multiplicative inverse is what you multiply to get 1. We are working under mod 19.

    Because \( 5 \times 4 \equiv 1 \pmod{19} \)

    \( 4^{-1} = 5 \)

  3. When is the formula \( a^{-1} \pmod{b} \) undefined? [ 1 mark ]

    4. When a and b are not co-prime. When the greatest common denominator of a and b > 1

  4. Prove the following conjecture: If \( 3 | n \) then \((n + 5)(n + 2) \equiv 1 \pmod 3 \) [ 2 marks ]

    5. If \(3 | n\), then \(n = 3i\). Thus,

    \( (3i + 5)(3i + 2) \equiv 1 \pmod 3 \)

    \( 9i + 6i + 15i + 10 \equiv 1 \pmod 3 \)

    \( 3(3i + 2i + 5i + 9) + 1 \equiv 1 \pmod 3 \)

    As any multiple of 3 is congruent with 0 modulo 3,

    \( 0 + 1 \equiv 1 \pmod 3 \) ∎

  5. Prove the following conjecture by induction: The formula \( (5n + 1)(n + 1)(2n + 3) \) is divisible by 3 for all positive natural numbers \( n \) [ 3 marks ]

    6. To prove this claim, we will prove a base case where \( n = 1 \) and an inductive step

    Base case, where n=1

    \( 3 | (5(1)+1)((1)+1)(2(1)+3) \)

    \( 3 | (5+1)(1+1)(2+3) \)

    \( 3 | (6)(2)(5) \)

    \( 3 | (3)((2)(2)(5)) \)

    To prove the inductive step, we assume the claim holds for a number \( n = k \), which would mean:

    \( 3 | (5(k)+1)((k)+1)(2(k)+3) \)

    \( 3 | (5k+1)(k+1)(2k+3) \)

    \( 3 | (5k+1)(2k^2 + 5k + 3) \)

    \( 3 | 10k^3 + 27k^2 + 20k + 3 \)

    Now, if the claim holds for \( n=k \), then we can show that for \( n = k + 1 \):

    \( 3 | (5(k+1)+1)((k+1)+1)(2(k+1))+3) \)

    \( 3 | (5k+6)(k+2)(2k+5) \)

    \( 3 | (5k+6)(2k^2 + 9k + 10) \)

    \( 3 | 10k^3 + 57k^2 + 104k + 60 \)

    As we assume \( 3 | 10k^3 + 27k^2 + 20k + 3) \), we can subtract this from our formula:

    \( 3 | (10k^3 + 57k^2 + 104k + 60) - (10k^3 + 27k^2 + 20k + 3) \)

    \( 3 | 30k^2 + 84k + 57 \)

    \( 3 | 3(10k^2 + 28k + 9) \) ∎

Algorithms [ 9 marks ]

  1. Simplify the following so that it is no longer uses sigma-notation: \( \sum_{i=1}^{n} (i + i^2 + 1) \) [ 2 marks ]

    2. \( \sum_{i=1}^{n} (i + i^2 + 1) = \sum_{i=1}^{n} i + \sum_{i=1}^{n} i^2 + \sum_{i=1}^{n} 1 \)

    \( = \frac{n(n+1)}{2} + \frac{n(n + 1)(2n+1)}{6} + n(1) \)

    \( = \frac{3n(n+1)}{6} + \frac{n(n + 1)(2n+1)}{6} + \frac{6n}{6} \)

    \( = \frac{ (n+1)(2n^2 + 4n) + 6n }{6} \)

    Or equivalent.

  2. What is the order of the following function in Big-Oh notation? \( T(n) = n^3 + n \log n + n \) [ 1 mark ]

    3. \( O(n^3) \)

  3. Put the following in order, slowest-growing first [ 1 mark ]
    • \( O(1) \)
    • \( O(\log n) \)
    • \( O(n) \)
    • \( O(n \log n) \)
    • \( O(n^2) \)
    • \( O(n!) \)

Here is the pseudo code for an algorithm

Function A(n):
    num := 0
    for (i = 1 to n)
        for (j = 1 to n)
            num := num + 1
        endfor
    endfor
return num
  1. Give the value \( A(10) \)? [ 1 mark ]

    2. 100

  2. Write a function named A in a programming language that implements this algorithm. [ 1 mark ]
    3. int A(int n)
{
    int num = 0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            num++;
    return num;
}
  3. Calculate the time function for the algorithm and express as a polynomial [ 2 marks ]

    4. \( \sum_{i=1}^{n} \sum_{j=1}^{n} c \)

    \( \sum_{i=1}^{n} nc \)

    \( c(\frac{n(n+1)}{2}) \)

  4. Give the time complexity of this time function [ 1 mark ]

    5. \( (n^2) \)

Part 2: Discrete Mathematics [ 25 marks ]

Propositional Logic [ 6 marks ]

De Morgan’s Laws of propositional logic relate conjunction and disjunction.

  1. Prove by means of a truth table that: \( \neg (p \wedge q) \iff \neg p \vee \neg q \) [ 1 mark ]
    2. p q \( \neg (p \wedge q) \) \(\neg p\) \(\neg q\) \(\neg p \vee \neg q \) \(\neg (p \wedge q) \iff \neg p \vee \neg q \)
    T T F F F F T
    T F T F T T T
    F T T T F T T
    F F T T T T T
  2. Prove by means of a truth table that: \( \neg (p \vee q) \iff \neg p \wedge \neg q \) [ 1 mark ]
    3. p q \( \neg (p \vee q) \) \(\neg p\) \(\neg q\) \( \neg p \wedge \neg q \) \(\neg (p \vee q) \iff \neg p \wedge \neg q \)
    T T F F F F T
    T F F F T F T
    F T F T F F T
    F F T T T T T

Modus Tollens is a rule of inference with the following form: “If P, then Q; and not Q; therefore, not P”

  1. Express Modus Tollens as a statement of propositional logic. [ 1 mark ]

    2. \( ( P \implies Q \wedge \neg Q ) \implies \neg P \)

  2. Modus Ponens is another rule of inference that we saw in the lectures. Express Modus Ponens as a statement of propositional logic. [ 1 mark ]

    3. \( ( P \implies Q \wedge P ) \implies Q \)

  1. In a sentence, and with reference to specific propositional logic operators explain why the proof of a contradiction in a foundational axiomatisation of mathematics is disasterous to its programme (assuming classical logic). [ 2 marks ]

When the antecedant of an implication (\( \implies \)) is false, the consequent is vaccuously true. Therefore from a contradiction, you can prove that any statement is true.

Set Theory [ 9 marks ]

Assume the domain is natural numbers (including 0). Given the sets

A = { 1, 2, 3 }
B = { 3, 4, 5, 6 }
C = { n | n < 4 }
D = { n | n ≡ 0 (mod 3)}

Give the extension of the following sets:

  1. \( A \cup B \) [ 1 mark ]
    2. \( \{ 1, 2, 3, 4, 5, 6 \} \)
  2. \( B \cap C \) [ 1 mark ]
    3. \( \{ 3 \} \)
  3. \( C \setminus D \) [ 1 mark ]
    4. \( \{ 1, 2 \} \)
  4. \(\mathbb{P}(A) \) [ 2 mark ]
    5. \( \{ \{1, 2, 3 \}, \{1, 2 \}, \{1, 3\}, \{2, 3\}, \{1 \}, \{2\}, \{3 \}, \emptyset \} \)
  5. \(A \times C \) [ 2 mark ]
    6. \( \{ (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3) \} \)
  6. \( \{ n : n \in \mathbb{Z} \wedge (n < 5 \vee n > -2) \wedge \neg (n = 0) \} \) [ 2 mark ]
    7. \( \{ -1, 1, 2, 3, 4 \} \)

Graph Theory [ 10 marks ]

Look at the following graph:

  1. Draw an adjacency matrix for this graph. [ 2 marks ]

    In along top, out down side

      n1 n2 n3 n4 n5 n6 n7
    n1   1 2 1      
    n2       1 2 1  
    n3 1         1 2
    n4              
    n5              
    n6              
    n7              
  2. Write out a sequence of nodes of this graph that form a cycle. [ 1 mark ]

    [n1, n3] or [n3, n1]

  3. Using set notation write out all the nodes of this graph with loops. [ 1 mark ]

    \( \emptyset \)

  4. What is the out-degree of node n3? [ 1 mark ]

    4

  5. What is the maximum degree of this graph? [ 1 mark ]

    6

A graph \( G = \{ (v, e) : v \in V \wedge e \in V \times V \} \) is defined for some set \( V \).

  1. Draw G for \( V = \{ n1, n2, n3 \} \) [ 1 mark ]
  2. Is G a connected graph? [ 1 mark ]

    3. Yes

  3. Is G a directed graph? [ 1 mark ]

    4. Yes

  4. Does G contain loops? [ 1 mark ]

    5. Yes

This is the end of the assessment.