アルゴリズムの設計と解析

教授： 黄 潤和 （W4022）rhuang@hosei.ac.jp

SA： 広野 史明 （A4/A10）fumiaki.hirono.5k@stu.hosei.ac.jp

Goal

2

到達目標：

The objectives of this course are to make students firmly laying

good foundation of data structures and algorithms, and one-step

further comprehensively understanding algorithm analysis and

having design and implementation skills in Python, Java, or

other programming language.

3

Contents (L1 - Introduction)

What is an Algorithm?

How to design?

How to analyze?

4

Why study algorithms?

Algorithms play the central role both in the

science

practice

From a practical standpoint- you have to know a standard set of important algorithms

- you should be able to design new algorithms

From theoretical standard - the study of algorithms is the core of computer science

related to many other fields

useful in developing analytical skills

5

Of computing

IntroductionWhat is an Algorithm?

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.

A. Levitin “Introduction to the Design & Analysis of Algorithms,” 3rd ed., Ch. 1 ©2012 Pearson Education, Inc. Upper Saddle River, NJ. All Rights Reserved.

合理的な

ambiguousあいまいな

The algorithm is independent from any programming languages.

7

Two main approaches

1. from typical problem types

2. from algorithm design techniques

8

1. from typical problem types

(a number of algorithms to a problem type)

9

10

Algorithm Features

11

Difference between Algorithm and Pseudocode

An algorithm is a formal definition with some specific characteristicsthat describes a process, which could be executed by a Turing-complete computer machine to perform a specific task. Generally,the word "algorithm" can be used to describe any high level task incomputerscience.

Pseudocode is an informal and (often rudimentary) humanreadable description of an algorithm leaving many granular details ofit. Writing a pseudocode has no restriction of styles and its onlyobjective is to describe the high level steps of algorithm in a muchrealistic manner in natural language.

12

Sorting

Searching (e.g. BFS, DFS, Red-black tree, 2-3-4 tree)

Shortest paths in a graph (e.g. Dijkstra’s algorithm)

Minimum spanning tree

(e.g. Prim’s algorithm, Kruskal’s algorithm )

Traveling salesman problem (TSP tour approximation)

Knapsack problem (Dynamic programming algorithm )

Chess

Primality testing

Towers of Hanoi

Program termination

Some Well-known Computational Problems

13

14

e.g. Sorting problemThere are many different algorithms

e.g. Greatest common factor

Problem: Find gcd(m,n),

the greatest common divisor of two nonnegative,

not both zero integers m and n

e.g.: gcd(60,24) = 12, gcd(60,0) = 60, …

(1) Euclid’s algorithm: it is based on repeated application of equality

gcd(m,n) = gcd(n, m mod n)

until the second number becomes 0,

which makes the problem trivial.

e.g.: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12

15

最大公約数

Other methods(to the same problem: Greatest common factor)

(2) Brute force solution

Step 1 Assign the value of min{m,n} to t

Step 2 Divide m by t. If the remainder is 0, go to Step 3;otherwise, go to Step 4

Step 3 Divide n by t. If the remainder is 0, return t and stop;otherwise, go to Step 4

Step 4 Decrease t by 1 and go to Step 2

(3) Finding the prime factors

Step 1 Find the prime factorization of m

Step 2 Find the prime factorization of n

Step 3 Find all the common prime factors

Step 4 Compute the product of all the common prime factorsand return it as gcd(m,n)

16

2. from algorithm design techniques

17

Divide and conquer

Decrease and conquer

Transform and conquer

Brute force

Greedy approach

Dynamic programming

Backtracking and branch-and-bound

Space and time tradeoffs

Some well-known algorithm design techniques

18

e. g. Divide and Conquer technique (分割統治) which is used in many different algorithms for solving different problems.

For example

- Searching

- Sorting

- Matrix multiplication

- ……

A design technique to solve different problems

19

Which is better?

Two main issues:

(1) How to design algorithms?

(solve the problem)

(2) How to analyze algorithms?

(evaluate/optimize the algorithms)

Algorithm design techniques

Brute force

Divide and conquer

Decrease and conquer

Transform and conquer

Space and time tradeoffs

Greedy approach

Dynamic programming

Iterative improvement

Backtracking

Branch and bound

……

20

Analysis of algorithms

How good is the algorithm? correctness

time efficiency

space efficiency

Does there exist a better algorithm? lower bounds

optimality

21

1-22

For example: sorting

Rearrange the items of a given list in ascending order.

Input: A sequence of n numbers <a1, a2, …, an>

Output: A reordering <a´1, a´2, …, a´n> of the input sequence such that a´1≤ a´2 ≤ … ≤ a´n.

Why sorting?

Help searching

Algorithms often use sorting as a key subroutine.

Sorting key

A specially chosen piece of information used to guide sorting. E.g., sort student records by student ID.

Analysis of Algorithms 23

An example:

Approach

Pseudo code

Analysis of Algorithms 24

the best-case running time is (n)

the best case occurs if the array is already sorted, t j =1

Algorithm

Analysis of Algorithms 25

A worst-case running time of (n2)

O(n2)bound on worst-case running time of insertion sort

Analysis of Algorithm 26

Running Time

Most algorithms transform input objects into output objects.

The running time of an algorithm typically grows with the input size.

Average case time is often difficult to determine.

We focus on the worst case running time. Easier to analyze

Crucial to applications such as games, finance and robotics

0

20

40

60

80

100

120

Ru

nn

ing

Tim

e1000 2000 3000 4000

Input Size

best case

average case

worst case

Monday, May 14,

2018

27

Experimental StudiesWrite a program implementing the algorithm

Run the program with inputs of varying size and composition

Use a method in Java like System.currentTimeMillis() or

to get an accurate measure of the actual running time

Plot the results

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

0 50 100

Input SizeT

ime

(m

s)

28

Comparison of different algorithms

Analysis of Algorithm 29

Big-Oh Notation

To simplify the running time estimation,

for a function f(n), we ignore the constants and lower order terms.

Example: 10n3+4n2-4n+5 is O(n3).

Monday, May 14, 2018

Analysis of Algorithm 30

Big-Oh Notation

To simplify the running time estimation,

for a function f(n), we ignore the constants and lower order terms.

Example: 10n3+4n2-4n+5 is O(n3).

Monday, May 14, 2018

Function of Growth rate

31

32

Some approximate of several functions important for analysis of algorithms

33

Efficiency is very much depended on data structure

Apart from the linked list, there are other often used data structure.

About this course

34

Reference book

Thomas H. Cor-men, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2009Anany Levitin, Addison-Wesley, 2011

Textbook

Anany Levitin, Addison-Wesley, 2011

About this course

Teaching plan

It is expected to have slight adjustments

Evaluation

- Mid-term: exercise problems (20%)

- Exams: final exam (80%)

35

Exercise 1-1

What is the output of Test1(200) ?

Test1（200）の出力結果は何ですか？

Test1は次のアルゴリズムです。

Algorithm Test1(n)

b 0

for i 1 to n do

if i mod 6 = 0 then b b + 1

else if i mod 9 = 0 then b b +10

return b

36

Exercise 1-2

What are the output of Test2(100)?

Test2（100）の出力結果は何ですか？

Test2は次のアルゴリズムです。

Algorithm Test2(n)b 0

for i 1 to n dofor j 1 to i do

b b +1return b

37

Exercise 1-3

What are the output of Test3(1000) ?

Test3（1000 ）の出力結果は何ですか？

Test3は次のアルゴリズムです。

Algorithm Test3(n)i 1b 0while i < n do

b b + 1i 2i

return b

38