Mathematical Algorithms and Methods

Question 1

Define clearly the terms perfect number, abundant number, semiperfect number and weird number

Answer 1

Perfect = sum of **proper** divisors equals the number
Abundant = sum of **proper** divisors in greater than the number
Semiperfect = the sum of **some** of the **proper** divisors equals the number
Weird = abundant but not semiperfect

Question 2

State the Fundamental Theorem of Arithmetic. Illustrate with an example of your choosing

Answer 2

A positive integer can be factorised as a product of primes in a unique way.

Question 3

State and give the general solution to the Diophantine equation
753x + 135y = 6

Answer 3

A solution of an ordinary differential equation of order n that involves exactly n essential arbitrary constants.

Question 4

Why does the similar Diophantine equation 753x + 135y = 5 not have a solution

Answer 4

5 is not a multiple of the gcd 3

Question 5

State and convert the decimal 121 into each of the bases binary, hexadecimal and base 7, show your working.

Answer 5

Binary: Is a system of numbers based on two symbols 0 and 1.

Hexadecimal: Is a system of numbers based on sixteen symbols. 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

Base 7: is a system that has 7 digits. 0, 1, 2, 3, 4 5 and 6. We count like this: 0. Start at 0.

1111001, 7D, 232

Question 6

Both add and multiply together base 8 numbers 352 and 17, show all workings.

Answer 6

Addition 371,
Multiplication 6666

Question 7

Define what is meant by 2’s complement in binary. Explain why it is useful for dealing with negative numbers and subtraction. Include examples to illustrate your explanation.

Answer 7

The way computers chooses to represent integers.

In two’s complement form, a negative number is the 2’s complement of its positive number with the subtraction of two numbers being A – B = A + ( 2’s complement of B ).

Subtraction of binary numbers can be done by adding the (2’s complement + 1) of the second number to the first number. Binary subtraction is just binary addition of a negative number.

Question 8

Consider the sets U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and subsets
A = {1, 2, 4, 8}, B = {2, 4, 6, 8, 10}, and C = {3, 4, 5, 6, 7}.

Determine the following:
 (A ∩ B ) ∪ C
 (A ∪ C)ˊ
 B \ C
 A ∆ C

Answer 8

{2, 3, 4, 5, 6, 7, 8}

{9, 10}

{2, 8, 10}

{1, 3, 5, 6, 7, 8}

Question 9

Consider the sets
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
and subsets
A = {1, 2, 4, 8}, B = {2, 4, 6, 8, 10},
and
C = {3, 4, 5, 6, 7}.

Calculate the power set P(A). In general, how many elements are in the power set of a set of cardinality n? How many elements are there in the Cartesian product A × A?

Answer 9

Question 10

For each of the following statements, either prove they are true or give an example to show they are false.

Answer 10

Question 11

Define clearly the terms injective, surjective, and bijective.

Answer 11

Injective – two things cannot map to the same thing, or f(x) = f(y) implies x = y. Surjective – For all y, there exists x such that f(x) = y. Bijective – both injective and surjective.

Question 12

Consider the function f

Answer 12

f(x) is none, g(x) is injective only.

Question 13

Calculate

Answer 13

Question 14

Explain briefly what is meant by O(n) notation (you do not need a formal definition). Illustrate your explanation with an example.

Answer 14

Big O notation describes the complexity of your code using algebraic terms.

Question 15

Find

Answer 15

Question 16

Draw the complete graph on 4 vertices. Is this graph planar?

Answer 16

Question 17

Define what is meant by a cycle, a tree, and a spanning tree.

Answer 17

Cycle – a path that returns to the same vertex with no other repeats.

Tree – a graph with no cycles.

Spanning tree – A subgraph that forms a tree

Question 18

What is the main difference between Prim’s algorithm and Kruskal’s algorithm? Illustrate with an example. Will they always give the same graph as their result?

Answer 18

Prim starts from the beginning and chooses the next shortest path from those already established (without creating a cycle) while Kruskal chooses from the shortest anywhere in the graph. Any example. Will not always be the same (although will be if the weights are all different).