# CS代考 COMP90038 – cscodehelp代写

COMP90038

Algorithms and Complexity

Lecture 1: Introduction

(with thanks to Harald Søndergaard)

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

Olya Ohrimenko Pan Lianglu

4

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Course Coordinator Lecturer Lecturer

Tutors:

Santa Maiti, Lianglu Pan, ,

Head Tutor

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, Piazza discussion board Tutorials start in week 2

6

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Assessment

10 Weekly Quizzes: Worth 10% of your grade

2 Assignments due around Week 6 and Week 11, worth 15% each

3-hour Final Exam: worth 60%

To pass the subject:

Hurdle: obtain at least 30/60 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, , 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 reasoning, that is, algorithms for logical formalisms, for example to decide “does this formula follow from that?”

24

Copyright University of Melbourne 2016, provided under Creative Commons Attribution License

Computability

2012: ’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 Divide and conquer Transform and Conquer …

Euclid’s Algorithm

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