ALGORITHMS AND COMPLEXITY
Click on Insert > new slide to choose your cover, then delete this page.
HIT220 Algorithms and Complexity
Week 1: Overview and Introduction to Algorithms
Cat Kutay
Click on Insert > new slide to choose your cover, then delete this page.http://www.nature.com/nature/journal/vaop/ncurrent/full/nature21416.html
http://www.nature.com/nature/journal/vaop/ncurrent/full/nature21416.html
Click on Insert > new slide to choose your cover, then delete this page.
How does Google Maps figure out how to get from CDU to the Airport?
••
Click on Insert > new slide to choose your cover, then delete this page.
They use Route finding Algorithms
Click on Insert > new slide to choose your cover, then delete this page.
How does Nasa choose how to arrange the solar panels on the International Space Station and when to rearrange them?
Click on Insert > new slide to choose your cover, then delete this page.
They use an optimization and a scheduling algorithms
Click on Insert > new slide to choose your cover, then delete this page.
Lecture Outline
• Introduction to HIT 220 • Contact details • Introduction to the course including your expectations and
required readings • Resources and skills required • Assessment Items • Learning Outcomes and Course outline
Click on Insert > new slide to choose your cover, then delete this page.
Unit Coordinator
• Unit Coordinator and Lecturer: DR Cat Kutay
cat.Kutay@cdu.edu.au
Ph: 08 8946 6669
• Office:
College of Engineering, IT & Environment
IT Discipline
Purple Building #12, Level 3, Office # 8 (12.3.8)
• Consultation hours:
Monday, Wednesday, Thursday. Also Friday morning
Click on Insert > new slide to choose your cover, then delete this page.
Tutoring Staff
• Tutor: William Lane
william.lane@cdu.edu.au
• Office:
Top End Language Lab
Northern Institute
IT Discipline
Office: Yellow 2.62
• Consultation hours:
4:00 PM-5:00 PM M-F, or by appointment
Click on Insert > new slide to choose your cover, then delete this page.
What I Will Do
• Be available and approachable
• Give prompt feedback
• Attempt to make teaching sessions interesting
• Challenge you to develop your skills and broaden your thinking
Click on Insert > new slide to choose your cover, then delete this page.
What I Expect You to Do
• Be available and approachable during class time
• Give prompt questions, answers and feedback
• Make teaching sessions interesting with examples from your experience
• Do the pre work and come with questions
Click on Insert > new slide to choose your cover, then delete this page.
Key expectations
A lot of students say this is a challenging unit. Some things that you can do to make the learning easier:
• Internals – Your prompt attendance at every workshop is appreciated. • Externals – Keep in contact via the discussion board and email. • Do keep up to date with the weekly work. Work with others in the unit. Revisit
the topics regularly.
• Ask questions, both in and out of class. Questions can be posted on the discussion board.
• Start early on assignments and attempt all questions. • Enjoy the subject!
Click on Insert > new slide to choose your cover, then delete this page.
Expectations and responsibilities
• Complete weekly readings, tutorial preparation and online activities/forum questions and discussions.
• Timely completion of assessments • Use LearnLine and your student email regularly. • Respect fellow students and lecturers • Provide feedback on the course to assist us to improve future offerings • Most Importantly: Do your best
Click on Insert > new slide to choose your cover, then delete this page.
Learnline (Online Learning System)
In this unit, Learnline will be used to: • Provide weekly reading and exercises to prepare for class on Friday • Provide access to online activities • Post announcements about the unit • Provide information about study requirements, including detailed
information about assessments
• Upload assessment items • Access feedback from tasks and grades for assessable work • Provide a communication point where you contribute to discussions as
part of your assessment, and to interact with other students in the unit.
• If necessary, emails should contain the unit code (HIT220)
Click on Insert > new slide to choose your cover, then delete this page.
Assessment Information
• Assessment rules • Plagiarism • Referencing requirements • Extensions and late submission • General Grading Scheme • Special consideration
Please refer to Assessment Overview and the Governance Library
Click on Insert > new slide to choose your cover, then delete this page.
Unit Description
• Explore and implement algorithms in order to solve complex computing problems in an efficient way.
• Develop algorithms and design techniques required in building and analysing the performance of a program to optimum efficiency.
• Implement the most appropriate existing algorithms and design techniques for any given computing problem.
Click on Insert > new slide to choose your cover, then delete this page.
1. Conduct a basic analysis of the algorithm that includes determining the time and space complexity analysis of the algorithms.
2. Solve elementary recurrence relations.
3. Use algorithmic strategies to solve different sets of given problems and compute the complexity analysis of your solution.
4. Evaluate the factors in the choice of algorithms such as computational efficiency, programming time, code complexity and maintainability.
5. Describe the distributed paradigm in coding and the relative ordering of events in a distributed algorithm.
6. Work with the concept of finite state machines.
Goal of the Unit
Click on Insert > new slide to choose your cover, then delete this page.
Student introductions
Click on Insert > new slide to choose your cover, then delete this page.
• Course structure (Flexible approach) • Lectures – 2 Hours
• Read appropriate chapter before class • Read lecture slides before class • Do exercises before class • Answer questions provided • Prepare your questions for class
• Labs/workshops – 2 Hours • Consultations
Course Details
Click on Insert > new slide to choose your cover, then delete this page.
• Each week, there are readings, lectures, workshops and exercises linked to in LearnLine. Exam questions can come from any of these sources.
• Workshops are not marked themselves and not otherwise required, the exam questions may be from material in those activities.
• Lectures and workshops may not be recorded, you need to attend, online or face-to-face
• Review your work each week before next week
Important things to note
Click on Insert > new slide to choose your cover, then delete this page.
• This course is based on action learning (Revans, 1980*) using a constructivist approach
L=P+Q+R
• Programmed knowledge • Explicit knowledge learned from others • Learning concepts and analysis techniques
• Questioning Insight • Making implicit knowledge more explicit • Learning by doing
• Reflection • Make sense of what you have done • Relate back to programmed knowledge
Learning Approach
* Revans, R. 1980. Action learning: New techniques for management. London: Blond & Briggs, Ltd.
Click on Insert > new slide to choose your cover, then delete this page.
• Confucius • I hear and I forget ; I see and I remember ; I do and I understand. • Assessment and teaching is based on doing rather than just listening
to lectures
• Insight is… • Combining your experience and things you know to create new
knowledge and apply it to new situations • Working in groups and reflecting (sharing and comparing) • Effective programming comes about by rigorously testing
assumptions about prior knowledge and questioning everything
Learning Approach
Click on Insert > new slide to choose your cover, then delete this page.
Have a question?
• If you have questions about course content, please post them in the discussion board to get help from others in the course. • For now will use weekly forums
Click on Insert > new slide to choose your cover, then delete this page.
Prior learning
• This is not a programming course but there is a requirement for programming knowledge and skills. Programming in any one of Java, Python, C or C++.
• This is not a mathematics course but mathematics is involved in almost all content of the course. Calculus is not needed but some maturity in problem solving and basic algebra is expected.
• Recommended that students in this unit should have completed at least 1 year of their degree.
Click on Insert > new slide to choose your cover, then delete this page.
Do you have prior learning needed?
• Any worries? Please discuss. External students should contact me by email
to clarify.
• All emails, should start with the subject word (HIT220)
Click on Insert > new slide to choose your cover, then delete this page.
Required readings
• Michael T. Goodrich, et al., Data Structures and Algorithms in Python, 1st Edition, John Wiley & Sons, Inc.
Click on Insert > new slide to choose your cover, then delete this page.
Further reading
• Michael T. Goodrich & Roberto Tamassia, Algorithm Design and Applications, 2015, John Wiley & Sons.
Click on Insert > new slide to choose your cover, then delete this page.
Originality & proper attribution
• Because so much information is online it can be easy to inadvertently import text into a written report without proper attribution
• The objective should be wherever possible to represent information in your own words (80-90% of a paper should be in your own words)
• However, the judicious & limited use of direct (word-for-word) “quotes” can be entirely acceptable providing there is proper attribution
• Paraphrased information must also be attributed • As a matter of course submitted written work is checked through
plagiarism software (Turnitin)
• Having to address plagiarism issues is extremely embarrassing for both teacher & student
Click on Insert > new slide to choose your cover, then delete this page.
Referencing
• This unit asks that you use the APA referencing style. If you want to use different referencing style you need to ask your Lecturer.
• Referencing Style Guidelines: CDU Library Guide
• APA Reference Generator (6th Ed) Online Tool
Click on Insert > new slide to choose your cover, then delete this page.
Unit structure
• During these seminars, the instructor and students will discuss the arguments, evidence, and implications addressed by that week’s readings
• The workshops are an opportunity to critically engage the issues at hand through lively discussion and debate, so students are expected to complete all of the required reading beforehand.
• You are expected to come to lecturers with the intention of actively participating • You will get out of the course what you are willing to put in • You need to actively explore the subject matter & fully utilise the expertise of the
academic staff
Click on Insert > new slide to choose your cover, then delete this page.
Unit structure cont.
• Constructive, verbal communication will help understanding by participation in workshop discussions throughout the semester.
• You will also participate in a lab exercise, which will help build your computer skills.
Click on Insert > new slide to choose your cover, then delete this page.
Participation
• For internal students, attendance to all scheduled classes is expected. • For external students, regular interaction via Learnline is expected.
External students are welcome to attend the internal lecture and tutorials classes if they are able.
• The recommended study commitment for all students is 12 hours per week, which includes the semester weeks, mid semester study period, revision week and examination period. For internal students, the recommended study commitment includes formal contact hours.
• Specific details of individual class times can be obtained by accessing the class timetable at:
http://www.cdu.edu.au/student-central/timetables
Click on Insert > new slide to choose your cover, then delete this page.
Unit schedule
Week No
Lecture Topics Tutorial Submission
1 Introduction to Algorithms Lab 1 2 Complexity Analysis Lab 2 3 Linked Lists- Single / Double Lab 3 4 Circular Lists Lab 4 5 Stacks and Queues Lab 5 Lab Assessment-01 6 Binary Trees Lab 6 7 Balancing a Tree / Heaps Lab 7
Mid Semester Break 8 Elementary Sorting Algorithms Lab 8 Lab Assessment-02 9 Efficient Sorting Algorithms Lab 9
10 Graphs Lab 10 11 Topological Sort Lab 11 Lab Assessment-03 12 In Class Revision
Note this proposed class schedule may change during the semester and it is the responsibility of the student to check the accuracy of important information (e.g. quizzes, submission dates, etc). Any changes will be announced on Learnline and during lectures.
Click on Insert > new slide to choose your cover, then delete this page.
Assessment Tasks
Description/Focus Due Date Length Value
1. Lab Assessment-01: Week 1 to Week 5 Learning Materials
Week 5 As required 10%
2. Lab Assessment-02: Week 6 to Week 8 Learning Materials
Week 8 As required 20%
3. Lab Assessment-03: Week 9 to Week 11 Learning Materials
Week 11 As required 30%
4. Oral Exam Self booked slot
week 12-13 20min 40%
Click on Insert > new slide to choose your cover, then delete this page.
• Further details of all assessment items will be given in the workshops and through Learnline as these items are made available to students.
• Submissions for these assessment items should be made via Learnline in either Microsoft Word or PDF format by the due date. Submissions in any other format will not receive any feedback, and they may not be able to be marked.
• Submission links will be placed on Learnline under “Submit Here” in the Assessment section as the assessments are given to students.
• Students should get into the habit of placing their full names & the unit code (HIT220) in the right hand side header or footer of all documents submitted to ensure all submitted work is clearly attributable.
• Students will book a 20min slot on a spread sheet for when you are available. You will need to prepare with examples of how the algorithms we study are used
Assessment item details
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.
Algorithm
• In Computer Science, an algorithm is a set of steps which allow a computer program to accomplish a specific task.
• Once you find a problem to solve, an algorithm is the procedure you develop or follow to solve the problem correctly in a finite number of steps.
• It is an exact specification of how to solve a computational problem.
• Algorithm should be developed in a way so that it can work for all possible inputs.
• Algorithms are developed based on the correlation or the properties of the input and the output.
Click on Insert > new slide to choose your cover, then delete this page.
Describing Algorithm
Algorithms can be implemented in any programming language.
Generally “pseudo-code” is used to describe algorithms.
Pseudo-code is a type of high level structured English to define algorithms without using the specific syntax of any given programming language.
Click on Insert > new slide to choose your cover, then delete this page.
You are writing a game and you want the user to be able to play against the computer, checkers games (like chess).
Computer scientists have figured out how to write Chess programs that never lose by using the minimax search algorithm to search through the huge tree of possible moves. If your game is similar to Chess, then you might be able to use algorithms based on these techniques. If not, then knowing the limitations of those algorithms might lead you to redesign your game if it requires having a skilled computer player.
Click on Insert > new slide to choose your cover, then delete this page.
Revise Python
Review Python Concepts. Variables Data Types Operators Control Flow Functions Scope OOP & Classes
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.
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) • If b>a GCD (a,b) = GCD (a,b-a) = c say So you can interate 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.
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.
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
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.
Euler’s Theorem
A connected graph has an Euler cycle if and only if every vertex has even degree. Euler proved that a necessary condition for the existence of Eulerian cycle is that all vertices in the graph have an even degree, and stated without proof that connected graphs with all vertices of even degree have an Eulerian cycle
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.
Thank you
cat.kutay@cdu.edu.au