15/07/2015

Mathematics for the new A Level

Computer Science
Sarah Shakibi

Contents of this course

• VECTORS
– What they are as mathematical entities
– Why are vectors required in programming?
– Vector addition, scalar multiplication and Dot Product
– Application to logical bitwise operations
• SET THEORY
– Mathematical notation of Set Theory
– The concept of Finite vs Infinite Sets
– Operations on Sets – Union, Intersection, Difference
– Application of the above to regular expressions
• FUNCTIONS
– Mathematical concept of functions as mappings from one set to another
– Various types of functions: linear, polynomial, exponential, logarithmic
– Algorithmic complexity: time vs space
– Big O notation as a tool for estimating Algorithmic Complexity

1
 15/07/2015

Session I

Set Theory

2
 15/07/2015

Why are sets important?

• Mathematics can get amazingly complicated
quite fast.
• Graph Theory, Abstract Algebra, Real
Analysis, Complex Analysis, Linear Algebra,
Number Theory, and the list goes on.
• But there is one thing that all of these share in
common: Sets.
• They are the building blocks of incredibly
complex structures in Mathematics

Basic Examples of sets

3
 15/07/2015

Set Notation

The curly brackets { } are sometimes called "set brackets“.

Finite/Infinite
• The first set {socks, shoes, watches, shirts, ...}
we call an infinite set
• the second set {index, middle, ring, little} we
call a finite set.

4
 15/07/2015

Numerical examples of sets

Well known Sets

• Natural numbers N = {0, 1, 2, 3, …}

• Integers Z = {…, -2, -1, 0, 1, 2, …}
• Positive Integers Z+ = {1, 2, 3, 4, …}
• Real Numbers R = {47.3, -12, , …}
• Rational Numbers Q = {1.5, 2.6, -3.8, 15, …}
• An Ordinal Number is a number that tells the position
of something in a list, such as 1st, 2nd, 3rd, 4th, 5th
etc.

5
 15/07/2015

Set Theory Notation

• Set: Collection of objects (“elements”)
• aA “a is an element of A”
“a is a member of A” or
‘a belongs to A’
• aA “a is not an element of A”
• A = {a1, a2, …, an} “A contains…”
• Order of elements is meaningless unless its an ordinal set
• It does not matter how often the same element is listed.

Rationals
We are now able to define the set of rational
numbers Q:
Q = {a/b | aZ  bZ+}
or
Q = {a/b | aZ  bZ  b0}

6
 15/07/2015

Irrational Numbers
• An Irrational Number is a real number that
cannot be written as a simple fraction

Examples

7
 15/07/2015

Famous irrational numbers

[Link]

8
 15/07/2015

The empty/null set

• The set of piano keys on

a guitar
• Another example of the
empty set are the set of
countries south of the
south pole.

9
 15/07/2015

Subsets (Proper & Improper)

•A  B “A is a subset equal of B”
•A  B if and only if every element of
A is also an element of B.
•We can completely formalize this:
•A  B x :xA xB

Worked Example
• Let A be all multiples of 4 and B be all
multiples of 2. (write these out using { } and
some positive, negative multiples of 4 and 2.)

• Is A a subset of B?
• And is B a subset of A?

10
 15/07/2015

Pairing off the members

A is a subset of B, but B is not a subset of A. How do we write this?

Proper Subset

Write out the second line as a FULL

English sentence.

11
 15/07/2015

Useful Rules – practice reading out

Transitive property of sets

More useful rules

•   A for any set A
• A  A for any set A

12
 15/07/2015

Venn Diagrams are very useful

13
 15/07/2015

UNION - OR

Soccer ∪ Tennis = {alex, casey, drew, hunter, jade}

INTERSECTION - AND

Soccer ∩ Tennis = {casey, drew}

14
 15/07/2015

DIFFERENCE- Minus
Soccer − Tennis = {alex, hunter}

SUMMARY

15
 15/07/2015

Worked Example – 3 sets

• S means the set of Soccer players
• T means the set of Tennis players
• V means the set of Volleyball players
Volleyball = {drew, glen, jade}

Union
SUTUV TUV

T ∪ V = {casey, drew, jade, glen}

16
 15/07/2015

Intersection

S∩V

S ∩ V = {drew}

Difference
• (S ∩ V) − T

(S ∩ V) − T = {}

17
 15/07/2015

Universal Set
U = {alex, blair, casey, drew, erin, francis, glen, hunter, ira, jade}

Cardinality of a set

18
15/07/2015

19
15/07/2015

20
 15/07/2015

Cartesian Product of n>=3 sets

21
 15/07/2015

Working backwards

Write out the elements

of the sets A and B and
their Cartesian product
as tuples.

A= {a,b,c}
B={1,2}

AxB=

Regular Expressions[1]

22
15/07/2015

23
 15/07/2015

Regex Meaning Strings produced

A|B|C A or B or C A,B,C
ABC A AND B AND C ABC
A*BC Zero or more A BC, ABC, AABC,
followed by B and C AAABC…..
A+BC One or more A and ABC, AABC,
B and C AAABC….
AB?C A and either zero or AC, ABC
one B and C

24
 15/07/2015

Regex in Python

25
 15/07/2015

Countably infinite sets

• Lemma : If S is both countable and infinite,
then there is a bijection between S and N

Session II

Vectors

26
15/07/2015

27
 15/07/2015

Vector Addition & Subtraction

28
 15/07/2015

For calculations break into x & y

components

Vector addition

29
 15/07/2015

Subtraction

30
 15/07/2015

Magnitude
• For any vector a, the magnitude is given by
|a|
• To calculate it use Pythagoras:

Vector multiplication by scalar

31
15/07/2015

32
15/07/2015

33
 15/07/2015

Linear Combinations of vectors- Hard

definition!

34
 15/07/2015

What are GF and GF(2)

• In honour of the French mathematician
Evariste Galois (Galois Theory) a field which
has a finite number of elements (ie a finite
field) is called a Galois Field
• GF(2) is a finite/Galois field with two elements
namely 0,1 ie Z(2)

Addition & Multiplication in Z(2) or

GF(2) or just mod 2
[Link]

+ (AND Gate/Truth 0 1
Table)
0 0 1
1 1 0 ( 2 mod 2 = 0)

X (XOR Gate/Truth Table) 0 1

0 0 0

1 0 1

35
 15/07/2015

Dictionaries
• Recall a list (array) in Python:

Python Dictionary
• A dictionary in Python allows you to use
anything not just numbers by creating an
association between them (a mapping)
• [[Link]]

36
 15/07/2015

Adding to dictionary
stuff[1]= ‘hello’
stuff[2]=‘great’

• In fact Dictionary is a cross between SQL and a

List!

• Dictionaries are another example of a data

structure, and like lists they are one of the most
commonly used data structures in programming.
• A dictionary is used to map or associate things
you want to store to keys you need to get them
• A very good example for teaching given here:
• [Link]
ml

37
 15/07/2015

Vectors in Python
• [Link]
• For magnitude, and operations
• Best website for advanced Python
• [Link]

4 Vectors

38
 15/07/2015

What are vectors and how are they

used in programming
• [Link]
what-are-vectors-and-how-are-they-used-in-
programming

Vectors in programming
• [Link]
vectors/
• [Link]
s-definitions/[Link]
• Interactive dot product- and cross product
• [Link]
maths-a-primer-for-games-
programmers/vector/#Dot

39
 15/07/2015

Session III

Functions & Functional Programming

Functions

RESULT

40
 15/07/2015

Note that ‘x’ is just a variable…

41
 15/07/2015

What do functions do/process?

• Numbers
• Letters
• Codes
• Sets
• Data

A function has special rules…

It MUST work for EVERY possible
input value allowed
(range will determine this)

It has only ONE RELATIONSHIP

for each input value

Formal Definition of a Function

A function relates each element

of a set with exactly one element
of another set (possibly the same
set) (DATA)

42
15/07/2015

43
15/07/2015

44
 15/07/2015

Domain, Co-Domain & Range

45
 15/07/2015

Many names!!!

46
 15/07/2015

Composition of Functions

47
 15/07/2015

Why is order important?

• Well, imagine the functions were machines ... the
first one melts a hole with a flame (only for
metal), the second one drills the hole a little
bigger (works on wood or metal)
• What you see at the end is a drilled hole, and you
may think "that should work for wood or metal".
• But if you put wood into g º f then the first
function f would make a fire and burn everything
down!

Example
• f(x) = x + 1/x
• g(x) = x2

Find g.f(x) and f.g(x)

Is g.f(x) = f.g(x)?

48
 15/07/2015

Summary
• "Function Composition" is applying one
function to the results of another.
• (g º f)(x) = g(f(x)), first apply f(), then apply g()

Worked Example
f(x) = 2x+3 and g(x) = x2
"x" is just a placeholder, and to avoid confusion
let's just call it "input":
f(input) = 2(input)+3
g(input) = (input)2

49
 15/07/2015

Reversing the order- not same!

What if we reverse the order of f and g?
(f º g)(x) = f(g(x))
First we apply g, then apply f to that result:

50
 15/07/2015

Factorial is recursive
n! = n × (n−1)!

Uses the ‘stack’ abstract data type for

calculations

51
 15/07/2015

Permutations
• [Link]
[Link]
• How many ways can first and second place be
awarded to 10 people?

Example 1. Five different books are on a shelf. In how

many different ways could you arrange them?

Answer. 5! = 1· 2· 3· 4· 5 = 120

52
 15/07/2015

Example 2
• Example 2. There are 6! permutations of the 6 letters of the word
square.
• a) In how many of them is r the second letter? _ r _ _ _ _
• b) In how many of them are q and e next to each other?
• Solution.
• a) Let r be the second letter. Then there are 5 ways to fill the first
spot. After that has happened, there are 4 ways to fill the third, 3 to
fill the fourth, and so on. There are 5! such permutations.
• b) Let q and e be next to each other as qe. Then we will be
permuting the 5 units qe, s, u a, r.. They have 5! permutations. But
q and e could be together as eq. Therefore, the total number of
ways they can be next to each other is 2· 5! = 240.

53
 15/07/2015

Big O notation
• Very useful resource (used in following slides)
• [Link]
2/07/comp-sci-101-big-o-notation/

54
15/07/2015

55
 15/07/2015

Interactive Plots
• [Link]
• Set Axes
• Plot these functions:

Big O Notation

56
15/07/2015

57
15/07/2015

58
 15/07/2015

Factorial function ( n!)

59
 15/07/2015

Scale of run-time

O(1)
• O(1) means that no
matter how large the
input is, the time taken
doesn’t change.
• O(1) operations run in
constant time. Some
examples of O(1)
operations are :
• Determining if a number
is even or odd.
• Using a constant-size
lookup table or hash
table.

60
 15/07/2015

O(log n)

• Any algorithm which cuts the problem in half each time

is O(log n).
• O(log n) operations run in logarithmic time - the
operation will take longer as the input size increases,
but once the input gets fairly large it won’t change
enough to worry about.
• If you double n, you have to spend an extra amount of
time t to complete the task. If n doubles again, t won’t
double, but will increase by a constant amount.
• Example: binary search

61
 15/07/2015

O(n)
• O(n) means that for every element, you are
doing a constant number of operations, such
as comparing each element to a known value.
• O(n) operations run in linear time - the larger
the input, the longer it takes, in an even
tradeoff. Every time you double n, the
operation will take twice as long.
• Example: Linear/Sequential Search for an item
in an unsorted list

62
 15/07/2015

O(n log n)
• O(n log n) means that you’re performing an O(log
n) operation for each item in your input. Most
(efficient) sort algorithms are an example of this.
• O(n log n) operations run in loglinear time -
increasing the input size hurts, but may still be
manageable.
• Every time you double n, you spend twice as
much time plus a little more.
• Examples of O(n log n): quicksort (in the average
and best case), merge sort.

63
 15/07/2015

O (n^2)
• O(n^2) means that for every element, you do
something with every other element, such as
comparing them.
• O(n^2) operations run in quadratic time - the
operation is only really practical up to a
certain input size.
• Every time n doubles, the operation takes
four times as long.
• Examples of O(n^2): Bubble sort

The following function is an example of an O(n2)

operation, where every element in an array is
compared to every other element :

64
 15/07/2015

O(2n )
• O(2n ) means that the time taken will double
with each additional element in the input data
set.
• O(2n )operations run in exponential time - the
operation is impractical for any reasonably
large input size n.
• An example of an O(2n )operation is the
Travelling Salesman’s Problem

Deriving the complexity of the

algorithm
• It is possible to look at the code and derive
the complexity :
• Simple assignment/comparison statement 
O(1) - Example: indexing an array
• An algorithm that loops through an array
accessing each data item once  O(n) –
example Linear Search

65
 15/07/2015

Deriving the complexity

• An algorithm with inner and outer loops will be
polynomial with runtime increasing depending on
the depth of nesting and number of loops 
average case O(n^2) – Example Bubble sort,
Selection Sort, Insertion Sort
• Adding a loop within the inner loop would make
this O(^3)
• An algorithm that uses recursion to call itself is
usually of order O(a^n) –intractable – cannot be
solved within polynomial time - TSP

Factorial (n!)

66
 15/07/2015

Search for a person

O(1) - No matter how many people we pass to this function, the time taken
won’t change, since we’re only looking at the first element.

Palindrome
• O(n) - a push() and
pop() are performed for
each character in the
string, and naive string
comparison (output ==
input) is also O(n).

67
 15/07/2015

Sum of divisors of a number

• O(n) - each number up
to n is examined to
determine if it is a
factor.

Word occurrence

O(n) - each word in the input phrase is compared to our target

word.

68
 15/07/2015

References
[1] Elementary Language Theory, R Backhouse, 2002

[Link]
n-regex-examples/

[Link]
/07/comp-sci-101-big-o-notation/

69