ALGORITHMS AND COMPLEXITY

Click on Insert > new slide to choose your cover, then delete this page.

Euclid’s Algorithm – missing slide

The greatest common divisor (or highest common factor) of integers a and b is the largest positive integer (D) that divides both A and B. • Notation GCD(a,b) or HCF(a,b) • Euclid noted that if b>a GCD (a,b) = GCD (a,b-a) =

c say So you can iterate over GCD for ever decreasing values until you find the actual GCD (with no remainder) An efficient way to do this is GCD(a,b ) = GCD (a,b mod a) – ie subtract a from b until less than a The extended Euclidean Algorithm or by reversing the above process, you find x and y such that ax + by = c where cis the GCD

Click on Insert > new slide to choose your cover, then delete this page.

Use in Cryptography

• the computation of the modular multiplicative inverse is an essential step in the derivation of key-pairs in the RSA public-key encryption method. • The extended Euclid Algorithm applied to two

coprime numbers will provide the modular multiplicative inverse

We have GCD (a, b) = xa + yb. GCD is 1 as co-prime – no common factor except 1 Inverse of a is x (mod b) in a multiplication sense

Click on Insert > new slide to choose your cover, then delete this page.

Give an example where it can be used for sorting data.

Why was this algorithm so important - it was the first example of

Euclid's algorithm

Click on Insert > new slide to choose your cover, then delete this page.

Greatest Common Divisor

• What is the GCD (12,8) • First lets write all of the factors out of the number 12

1, 2, 3, 4, 6,12

• The factor of the number 8 1, 2, 4, 8

• The common factors between 12 and 8 are: 1, 2, 4

• The greatest common factor is: 4 • GCD (12, 8) = 4 • Write pseudocode for an algorithm yourself before you go to next slides

Click on Insert > new slide to choose your cover, then delete this page.

GCD pseudocode

Algorithm of finding GCD (Greatest Common Divisor)

1. Input a and b.

2. Set the value of x to a and the value of y to b.

3. If x>y then set x to x-y.

4. Else if x<y then set y to y-x.

5. Repeat steps 3 and 4 until x=y.

6. Output x (or y) and halt.

Task 1: Write the above pseudo-code into your preferred programming language.

Click on Insert > new slide to choose your cover, then delete this page.

Exercise

Prove 1: • The pseudocode (and the python program

attached on online page) will find the GCD as described on the ”missing slide” above

Prove 2: • Prove this GCD is the greatest common divisor

of the two number (a,b)

Click on Insert > new slide to choose your cover, then delete this page.

Task 1: Solution

Refer to slide notes for actual Python code.

Click on Insert > new slide to choose your cover, then delete this page.

A high level description of an colouring algorithm

Input: A graph G=(V,E)

Output: A 2-colouring, if one exists.

Method: An adaptation of Breadth First Search (BFS).

We study BFS in detail later but are using the idea of it now.

1. Choose any vertex and colour it RED.

2. Colour all the neighbours BLUE

3. Colour all the neighbours of BLUE vertices RED

4. Continue until vertices are coloured.

While assigning colours, if we find a neighbour which is coloured with same colour as the current vertex, then the graph cannot be 2-coloured.

Discuss: Is this pseudocode? Is this algorithm efficient?

A clear enough description at this point. Insufficient to fully describe the complexity which will also depend on the choice of data structure.

Take away from your activity that there is an efficient algorithm to establish whether or not a graph has a 2-colouring. On the other hand, 3-colouring is apparently much harder.

Click on Insert > new slide to choose your cover, then delete this page.

Breadth and Depth first search

• Find properties of graphs • Levels • Vertices • Edges

• Find paths in graph

• BFS and DFS: • Which is most time efficient? • Which is most space efficient?

Click on Insert > new slide to choose your cover, then delete this page.

2 colouring

• Step through this graph to show is 2- colourable

Click on Insert > new slide to choose your cover, then delete this page.

3- colour

• Step through this graph to show you need 3- colours