Assessment 1

Rubric

The coursework for this module is split into two. This is the first item of coursework for this module. It is worth 60% of the total module mark. The second item of coursework will be released later in the term and will be due in January and will be worth 40% of the total module mark.

In this assessment you will work on your own to demonstrate your understanding of the mathematical topics taught in this course. You will do this through a combination of solving mathematical problems, and implementing mathematical operations in a programming language.

Learning Outcomes

Your performance in this coursework will be assessed on the following Module Learning outcomes:

  1. Understand and use basic mathematical terminology.
  2. Comprehend the basic mathematical concepts that relate to Computer Science
  3. Apply mathematical concepts to Computer Science problem solving
  4. Understand the mathematical underpinning of Computer Science and be able to identify these

Submission and deadline

The coursework must be submitted by 12:00pm (noon) Friday 11 December 2020. The submission is via the module’s Moodle page. The submission point can be found under the ‘Assessment’ heading.

Acceptable Submission Formats

Submissions should be in the form of a .zip archive containing two files:

  1. A PDF containing the answers to all written questions.
  2. A Main.java file containing all code written in Java, and/or a main.py file containing all code if written in Python. Other programming languages may only be used with prior agreement with the course tutor.

Only code in the correctly named functions (as given in the question) will be marked. Other code, including code in public static void main(String[] args) will not be marked.

Please check your final submission to ensure that the formatting of any mathematical symbols is correct. Where appropriate handwritten submissions are acceptable, though these should be scanned and converted into PDF files. Image formats such as .jpeg, .png etc are not acceptable submission formats for such coursework.

Code Template

Template code for Java can be found at the following URL:

https://repl.it/@davidgundry/MathsForCSAssessmentTemplate

Marking

This coursework has a total of 60 marks available.

  1. The first part, Number Theory, is worth a total of 35 marks.
  2. The second part, Discrete Mathematics, is worth a total of 25 marks.

This coursework is worth 60% of the total mark for the module.

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 ]
  2. What is the result of \(10101010 \times 101 \)? You must show your working to get the mark. [ 1 mark ]
  3. What is the remainder and quotient of the following: \( 111010 \div 101 \)? You must show your working to get the mark. [ 2 marks ]

  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)

 /**
 * 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)
  1. What is the base 4 number `132` in hexadecimal? You must show your working to get the mark. [ 1 mark ]

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- = 666
--------- = 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. [ 7 marks ]
    /** 
    * Convert unix file permissions string to number
    * @param permissions - unix file permissions string such as `rw-rw-r--`
    * @return An integer expressing the equivalent octal value
    **/ 
    static int filePermissionsToNumber(String permissions)

    /** 
    * 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)

Modular Arithmetic [ 8 marks ]

  1. Give a value for \( a \) such that: \( (4 + 2) \bmod a \times 10 \bmod a - 5 \bmod a \equiv 0 \pmod{a} \) [ 1 mark ]
  2. What is \( 4^{-1} \pmod{19}\)? [ 1 mark ]
  3. When is the formula \( a^{-1} \pmod{b} \) undefined? [ 1 mark ]
  4. Prove the following conjecture: If \( 3 | n \) then \((n + 5)(n + 2) \equiv 1 \pmod 3 \) [ 2 marks ]
  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 ]

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. What is the order of the following function in Big-Oh notation? \( T(n) = n^3 + n \log n + n \) [ 1 mark ]
  3. Put the following in order, slowest-growing first [ 1 mark ]
    • \( O(n) \)
    • \( O(n \log n) \)
    • \( O(n^2) \)
    • \( O(n!) \)
    • \( O(\log n) \)
    • \( O(1) \)

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. Write a function named A in a programming language that implements this algorithm. [ 1 mark ]
  3. Calculate the time function for the algorithm and express as a polynomial [ 2 marks ]
  4. Give the time complexity of this time function [ 1 mark ]

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. Prove by means of a truth table that: \( \neg (p \vee q) \iff \neg p \wedge \neg q \) [ 1 mark ]

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 in propositional logic. [ 1 mark ]
  2. Modus Ponens is another rule of inference that we saw in the lectures. Express Modus Ponens in propositional logic. [ 1 mark ]
  1. In a sentence, and with reference to specific propositional logic operators explain why the existance of a contradiction in a foundational axiomatisation of mathematics is disasterous to its programme (assuming classical logic). [ 2 marks ]

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

Graph Theory [ 10 marks ]

Look at the following graph:

  1. Draw an adjacency matrix for this graph. [ 2 marks ]
  2. Write out a sequence of nodes of this graph that form a cycle. [ 1 mark ]
  3. Using set notation write out all the nodes of this graph with loops. [ 1 mark ]
  4. What is the out-degree of node n3? [ 1 mark ]
  5. What is the maximum degree of this graph? [ 1 mark ]

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. Is G a directed graph? [ 1 mark ]
  4. Does G contain loops? [ 1 mark ]

This is the end of the assessment.