ALGORITHMS AND COMPLEXITY
Click on Insert > new slide to choose your cover, then delete this page.
Introduction to Algorithms
Click on Insert > new slide to choose your cover, then delete this page.
Outline
Algorithms and complexity more generally through activities and problem solving. • Pseudocode • Euclid Algorithm • Colouring Maps and Graphs: same problem • Euler’s Theorem • Intro to Graph Theory • Binary Search • Breadth and Depth first search
Click on Insert > new slide to choose your cover, then delete this page.
Not all algorithms are created equal. What make a good algorithm?
1- Correctness 2- Efficiency
Which one more important??? 1 or 2 In some cases: good is good enough
Click on Insert > new slide to choose your cover, then delete this page.
Data structures and algorithms
• An algorithm is a step-by-step finite set of operations to solve a computational problem. Importantly, an algorithm always terminates and returns its answer.
• A data structure is an arrangement of data in computer memory. e.g. arrays, linked lists, queues, stacks, binary trees, hash tables, graphs.
• Algorithms are used to manipulate the data contained in these data structures. e.g. inserting, deleting, searching and sorting.
• Many algorithms apply directly to a specific data structures. • Typically there trade offs in efficiency of algorithms. Close connection between
choice of data structure and algorithm.
• Chapters 1, 3 to 8, present a number of different data structures and the algorithms that operate on them. In addition, the efficiency of each algorithm is analysed. Efficiency – time and space complexity.
Click on Insert > new slide to choose your cover, then delete this page.
Data structures and algorithms Some Characteristics of Data Structures
Table retrieved from https://web.archive.org/web/20180828031358/http://www.idevelopment.info/data/Programming/da ta_structures/overview/Data_Structures_Algorithms_Introduction.shtml
Data Structure Advantages Disadvantages
Array Quick inserts Fast access if index known<
Slow search Slow deletes Fixed size
Ordered Array Faster search than unsorted array Slow inserts Slow deletes Fixed size
Stack Last-in, first-out acces Slow access to other items
Queue First-in, first-out access Slow access to other items
Linked List Quick inserts Quick deletes
Slow search
Binary Tree
Quick search Quick inserts Quick deletes (If the tree remains balanced)
Deletion algorithm is complex
Red-Black Tree
Quick search Quick inserts Quick deletes (Tree always remains balanced)
Complex to implement
2-3-4 Tree
Quick search Quick inserts Quick deletes (Tree always remains balanced) (Similar trees good for disk storage)
Complex to implement
Hash Table Very fast access if key is known Quick inserts
Slow deletes Access slow if key is not known Inefficient memory usage
Heap Quick inserts Quick deletes Access to largest item
Slow access to other items
Graph Best models real-world situations Some algorithms are slow and very complex
Click on Insert > new slide to choose your cover, then delete this page.
Algorithms and complexity (more generally)
• Algorithms and data structures can be implemented in any programming language. • A description of an algorithm is presented in
pseudocode. This provides an informal high-level description of an algorithm. • Step-by-step, typically a mixture of English,
mathematics and programming constructs. • This level of detail should allow analysis of the
efficiency of the algorithm. • Will cover Time and space complexity next week
Click on Insert > new slide to choose your cover, then delete this page.
Greatest Common Divisor
• 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) • 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 slide
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
GCD (a, b) = xa + yb. GCD is 1 as co-prime Modular inverse of a is x (mod b)
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.
Task 1: Solution
Refer to slide notes for actual Python code.
Click on Insert > new slide to choose your cover, then delete this page.
Euclidean Algorithm for GCD
• The Euclidean Algorithm is a technique for quickly finding the GCD of two integers.
• Khan Academy https://www.khanacademy.org/computing/computer- science/cryptography/modarithmetic/a/the-euclidean-algorithm
• Youtube Mathtrain (Neat examples) https://www.youtube.com/watch?v=AJn843kplDw
Click on Insert > new slide to choose your cover, then delete this page.
Activity - Graph colouring
• The mapping problem • Colour a graph (see file graph 2-colouring) • Find the minimum number of colours needed so that each pair of adjacent
vertices (dots) has a different colour.
• Describe the idea of an algorithm which determines whether or not any given graph can be 2-coloured.
• Consider the larger graph (file graph 3-colouring) Is it possible to rule out using just 2 colours for this graph? Explain.
Finding a 3-colouring is not likely to be easy.
Challenge: Find a 3-colouring.
• Ask someone to verify your 3-colouring is a proper colouring? i.e. That every pair of adjacent vertices (dots) has a different colour. Describe an efficient algorithm for checking a claimed 3-colouring.
We will reflect on the outcomes of these colouring activities a few times over the course. Next week we consider graph colouring algorithms in the context of complexity classes P and NP.
Click on Insert > new slide to choose your cover, then delete this page.
A high level description of an 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.
Graphs - Informally
• A collection of vertices connected by edges.
• Vertices symbolise specific entities. • Edges between vertices denote
relationships.
Graphs are used to model a wide variety of situations.
Graphs are a highly important structure. We will study a range of graph algorithms over the course.
Example 1
The results of a tournament between players A,B,C,D
An example of a directed graph. Each edge has direction.
Click on Insert > new slide to choose your cover, then delete this page.
• Locations on a map, as in the classic problem of the bridges of Königsberg solved by Euler in 1736.
• Can one walk once and only once across each of the bridges of Königsberg and finish back at the starting point?
• Land masses are represented by vertices. Undirected edges represent the bridges.
Example 2
https://www.youtube.com/watch?v=W18FDEA1jRQ
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.
Guessing Game: Find my number Divide and Conquer
How many guesses did it take you to find the number this time? Why should you never need more than 9 guesses? (Can you think of a mathematical explanation)
I am thinking of a number between 1 and 300. You may ask, repeatedly, “Is the number less than ___?” I will answer Yes or No.
Binary search is a classic example of a “divide and conquer” algorithm. Logarithmic time complexity. (Efficient).
Click on Insert > new slide to choose your cover, then delete this page.
• Representation of chemical compounds such as Butane.
Graphs – Informally
• A graph presents an overall view of the problem • Abstract representation
exposes the important structure of the problem • Provides a valuable guide
for intuition and reasoning
Example 3
Click on Insert > new slide to choose your cover, then delete this page.
• A graph is a set of points called vertices or nodes, which are connected by a set of lines called edges or arcs. Thus for a graph G we denote the vertex set by V and the edge set by E and write G = (V, E).
Example 4
A simple graph is one that
has no loops or parallel edges
Some Graph terminology – also see graph theory definitions
Click on Insert > new slide to choose your cover, then delete this page.
Which are simple graphs?
Graphs (a) to (d) are simple.
Graphs (e) and (f) have parallel edges.
Graph (f) has loops. i.e. edges whose two end points are the same vertex.
Diagram can be found in your text. Mostly we will only be concerned with simple graphs.
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.
Thank you
cat.kutay@cdu.edu.au