COMP90038
Algorithms and Complexity
Lecture 1: Introduction
(with thanks to Harald Søndergaard)
Toby Murray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
What we will learn about
Data structures: e.g. stacks, queues, trees, priority queues, graphs Algorithms for various problems: e.g. sorting, searching, string
manipulation, graph manipulation, …
Algorithm Design Techniques: e.g. brute force, decrease-and-conquer, divide-and-conquer, dynamic programming, greedy approaches
Analytical and empirical assessment of algorithms Complexity classes
• •
•
• •
Textbook
Anany Levitin. Introduction to the Design and
Analysis of Algorithms, 3rd Edition, Pearson 2012
See also “Reading Resources” on LMS
3 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Staff
Toby Murray Andres Munoz Acosta Pan Lianglu
Course Coordinator Lecturer Head Tutor Lecturer
Tutors:
Annie Zhou, Assaf Dekel, Damayanthi Herath,
Nikolas Makasis, Oscar Correa Guerrero, Partha De,
Sameendra Samarawickrama, Yankun Qiu, Zheyu Ji
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
LMS, Lectures, Tutorials
• •
•
Primary on-line resource for the subject
Announcements, lecture slides, recordings, tutorials, assignments, weekly
quizzes, discussion board Tutorials start in week 2
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Assessment
Quizzes: one each week. Due by Tuesday of following week.
You MUST complete at least 8 quizzes to sit the final exam.
2 Assignments due around Week 6 and Week 11, worth 30% together 3-hour Final Exam: worth 70%
To pass the subject:
•
•
•
• • • • •
complete at least 8 of the Week 2 — 12 quizzes obtain at least 35/70 in the final exam
obtain at least 50/100 overall
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Time Commitment
•
•
•
•
On average: 10 hours per week Commitment is worth it
Expect to spend:
34 hours in lectures + tutes
30 hours on assignments
24 hours reading and reviewing 24 hours on tute prep
8 hours on quizzes and discussion
• • • •
What you learn here will form the foundations of a career in software, IT,
•
computational science, engineering, etc.
8
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Assumed Knowledge
There are two diagnostic quizzes for Week 1
not compulsory, but to help you work out how well you know the assumed Mathematics (sets, relations, functions, recurrence relations)
Programming (arrays, records, linked lists, dictionaries, functions, procedures, formal and actual parameters, parameter passing, return- values, pointers / references
•
•
background knowledge
•
•
See the Reading Resources page on the LMS which has some pointers to
•
online resources to help with this background knowledge
9
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How to Succeed
Understand the material (by doing), don’t just memorise it
If you fall behind, try to catch up as soon as possible
Don’t procrastinate, start early
Attempt the tutorial questions every week, before you attend the cute Use the LMS discussion board
Ask questions
Answer others’ questions
We are all on the same learning journey and have the same goal!
• • • • •
• •
•
10
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Introduction
•
Introduce yourself to your neighbours
Tell them where you are from, what degree you are doing, which
•
programming languages you know, what music you listen to, whatever
11
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
A Maze Problem
A maze (or labyrinth) is contained in a 10 x 10 rectangle, with rows and
•
columns numbered from 1 to 10
•
•
•
It can be traversed along rows and columns, moving: up, down, left, right The starting point is (1,1); the goal point is (10,10)
These points are obstacles that you cannot pass through:
(3,2) (6,6) (2,8) (5,9) (8,4) (2,4) (6,3) (9,3) (1,9) (3,7) (4,2) (7,8) (2,2) (4,5) (5,6) (10,5) (6,2) (6,10) (7,5) (7,9) (8,1) (5,7) (4,4) (8,7) (9,2) (10,9) (2,6)
Find a path through the maze
•
How did you go?
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How did you go?
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How did you go?
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How did you go?
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
How did you go?
16 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
17
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology: Problem
Algorithmic problem is one that can be solved mechanically (i.e. by a computer program)
Usually we want to find a description of a single generic program that can solve a bunch of similar problems
e.g. the “maze problem” is to come up with a mechanical solution to any particular maze
The maze we solved is called an instance of the maze problem
A problem may have many (even infinitely many) instances Algorithmic problem: a family of instances of a general problem
•
•
•
• • •
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Algorithmic Problems
• •
•
Algorithmic problem: a family of instances of a general problem
An algorithm for a problem has to work for all possible instances (i.e. for all
possible inputs)
Example: the sorting problem
• Instance is a sequence of items to sort Example: graph colouring problem
• Instance is a graph
Example: equation solving problem
•
•
•
Instance is a set of, say, linear equations
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Terminology: Algorithm
Dictionary definition: “process or rules for (esp. machine) calculation etc.” A finite sequence of instructions, with
no ambiguity: each step is precisely defined.
It should work for all (well-formed) inputs
It should finish in a finite (reasonable) amount time
•
•
•
• •
The (single) description of a process that will transform arbitrary input to the
•
correct output—even when there are infinitely many possible inputs
Like a cookbook recipe? Sort of, but more like a general “method”, a
•
systematic approach that works for any instance
20
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Algorithm: Euclid’s
Once, “algorithm” meant “numeric algorithm”.
•
Mathematicians developed many clever algorithms for solving all sorts of
•
numeric problems
•
• • •
The following algorithm calculates the greatest common divisor of positive Euclid’s Algorithm.
•
integers m and n, which we write as gcd(m,n). The algorithm is called
To find gcd(m,n):
Step 1: if n = 0, return the value of m as the answer and stop
Step 2: Divide m by n and assign the remainder to r.
Step 3: Assign the value of n to m, and the value of r to n; go to Step 1.
Example: gcd
Let’s run this on some example inputs:
Euclid(m,n) = while n ≠ 0
r ← m mod n m←n
n←r
return m
24 60
rmn
24 60 24
12 24 12
0 12 0
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: gcd
Let’s run this on some example inputs:
Euclid(m,n) = while n ≠ 0
r ← m mod n m←n
n←r
return m
171 7
rmn
373
131
010
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Non-Numeric Algorithms
350 years ago, Thomas Hobbes, in discussing the possibility of automated
•
reasoning, wrote:
“We must not think that computations, that is, ratiocination, has place only in numbers.”
Today, numeric algorithms are just a small part of the syllabus in an
•
algorithms course
(The kind of computations that Hobbes was really after was mechanised “does this formula follow from that?”
•
reasoning, that is, algorithms for logical formalisms, for example to decide
24
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Computability
2012: Alan Turing’s 100th birthday
•
When Turing was born, “computer” meant a human
•
who was employed to do tedious numerical tasks
•
Turing’s legacy: “Turing machine”,
“Church-Turing thesis”, “Turing reduction”,
“Turing test”, “Turing Award”.
One of his great accomplishments was to put the concept of an algorithm on have algorithmic solutions
•
firm foundations and to establish that certain important problems do not
25
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Abstract Complexity
In this course, we are interested only in problems that have algorithmic
•
solutions
However, amongst those, there are many that provably do not have efficient
•
solutions
Towards the end of the subject, we briefly discuss complexity theory—this
•
theory is concerned with the inherent “hardness” of problems
26
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Why Study Algorithms?
Computer science is increasingly an enabler for other disciplines, providing
•
useful tools for these
Algorithmic thinking is relevant in the life sciences, in engineering, in
•
linguistics, in chemistry, etc.
Today computers allow us to solve problems whose size and complexity is
•
vastly greater than what could be done a century ago
•
The use of computers has changed the focus of algorithmic study completely, because algorithms that work for a human (small scale) usually do not work well for a computer (big scale)
Algorithm Complexity
Two implementations of gcd:
Time to compute gcd(2147483647,2147483646) 3 minutes 19 seconds 0.033 seconds
We would like to predict how long an algorithm will take to run as the size of its input increases.
27 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Studying Algorithms and their Complexity
• • • • •
To collect useful problem solving tools
To learn, from examples, strategies for solving computational problems
To be able to write robust programs whose behaviour we can reason about To develop analytical skills
To learn about the inherent difficulty of some types of problems
29
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Problem Solving Steps
1. 2.
3. 4. 5. 6. 7. 8.
Understand the problem
Decide on the computational means (sequential vs parallel, exact vs. approximate)
Decide on the method to use (the algorithm design technique or strategy) Design the necessary data structures and algorithm
Check for correctness, trace example input
Evaluate analytically (time, space, worst case, average case)
Code it
Evaluate it empirically
Empirical Evaluation of gcd
30 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
31
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
What we will study
• •
Algorithm analysis
Important algorithms for various problems, namely:
Sorting
Searching
• String processing
Graph algorithms Approaches to algorithm design:
• •
•
•
• Brute force brute force gcd
• Decrease and conquer
…
Euclid’s Algorithm
•
Divide and conquer
•
• Transform and Conquer
32
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Study Tips
Before the lecture, as a minimum make sure you read the introductory section of the relevant chapter
Always read (and work) with paper and pencil handy; run algorithms by hand
Always have a go at the tutorial exercises; this subject is very much about learning-by-doing
After the lecture, reread and consolidate your notes
Identify areas not understood, use the LMS discussion board Rewrite your notes if that helps
•
• •
• • •
33
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Things to do First
Take the two Week 1 diagnostic quizzes on the LMS
Get the textbook, read Chapter 1, skim Chapter 2
Make sure you have a unimelb account
Visit COMP90038 LMS page, check the weekly schedule, any new announcements
• • • •
Use LMS discussion board, e.g. if you’re interested in forming a study group
•
with like-minded people, the Discussion Board is a useful place to say so