Alogaritma

Algorithm: the Basics Budi Hartono, ST, MPM Simulation Laboratory, UGM

Process, Instruction & Action 

Algorithm = logical sequences 

  

The instruction t0 = state - before the action action t1 = state - after

Example

A

B

t0

A ACTION

t0 : A contains yellow, B contains blue 1. Pour the blue water to C 2. Pour the yellow water to B 3. Pour the blue water to A t1 : A contains blue, B contains yellow

B

t1

Algorithm Exchange_the_contents

Top-down design  General

First, then go details

1

2

3

4

5

10

15

5

17

2

N=5 Order from the smallest value

- Iterations  N-1 times - Find the smallest - Position exchange

1

2

3

4

5

10

15

5

17

2

N=5

Pass k = 1 Find the smallest value, from N = 1 to N = 5 1

2

3

4

5

10

15

5

17

2

Exchange the location 1

2

3

4

5

2

15

5

17

10

Result, min = 2

1

2

3

4

5

2

15

5

17

10

N=5

Pass k = 2 Find the smallest value, from N = 2 to N = 5 1

2

3

4

5

2

15

5

17

10

Result, min = 5

Exchange the location 1

2

3

4

5

2

5

15

17

10 And so on

The initial & final states: 

T0 : random sequence of values 



Algorithm Data_Order

T1 : ordered sequence of values

Where: Algorithm Data_Order

Given N random data. Order them so that data#1 < data #2 < … < data #N Description: For pass k = 1,2, …, N-1 1. Find the smallest value (min) from k = 1 to k = N 2. Exchange min with data#k

START k = k+1 1. Find min

2. Position min @ k

K=4 ? YES STOP

1. Find min • Not detail enough • Must be refined Refining Step-1 1.1 Assume data #k is the min (temporary) 1.2 compare min with data #j; where j =(k+1), (k+2), .. , N if data #j < min, then data #j becomes the new min Refining Step-1.2 1.2.1 For j = (k+1), (k+2), …, N do: if data #j < min then data #j becomes the new min

2. Position min @ k Refining: 2.1 put data #k to a temporary place (temp) 2.2 put the min on the place of the data #k (formerly) 2.3 put the temp on the min (formerly)

The final algorithm Algorithm Data_Order Given N numbers of random data. Make an order of data so that: data#1 < data #2 < … < data #N  Description: 

For pass k = 1,2, …, N-1, do the following: {1. Find the smallest value (min) from k = 1 to k = N} 1.1 assume that data #k is the min 1.2 For j = (k+1), (k+2), …, N do: if data #j < min then data #j becomes the new min {2. Exchange min with data#k } 2.1 put data #k to a temporary place (temp)

2.2 put the min on the place of the data #k (formerly) 2.3 put the temp on the min (formerly)

I leave the flowchart for the next week’s homework

Basic Structures of Algorithms  Sequence  Selection  Repetition

Basic Structures of Algorithms

A1

Sequence

A1

A2

A3

A3

A2

A4

A4

THE RESULT ?

A

B

C

Basic Structures of Algorithms

Selection

 Conditions  Recall:

if data #j < min then data #j = new min  The general structure If condition then action

Basic Structures of Algorithms

Selection

 Example  If

Amir wins the competition then daddy will give him a new car  If Malioboro gets a traffic jam then go to Jl. Ahmad Dahlan  Your

example …

Basic Structures of Algorithms

Selection

 Another

structure If condition then action 1

else action 2  indenting  Your

example …

Basic Structures of Algorithms

 An

Repetition

advantage of using computers:

 Do

repetitive jobs without getting bored  Precision I

promise that I will never forget to do my homework 100 times !!!

Basic Structures of Algorithms

Repetition

Algorithm Writing_500_sentences Description

8.

Write “I promise that I will never forget to do my homework” Write “I promise that I will never forget to do my homework” Write “I promise that I will never forget to do my homework” Write “I promise that I will never forget to do my homework” Write “I promise that I will never forget to do my homework”

… 500

Write “I promise that I will never forget to do my homework”

4. 5. 6. 7.

???

Basic Structures of Algorithms

Repetition

Algorithm Writing_500_sentences Description: sentenceNumber = 0 repeat write “I promise that I will never forget to do my homework” sentenceNumber = sentenceNumber +1

until sentenceNumber = 500

Basic Structures of Algorithms

 General

Repetition

Structure

Repeat action Until condition

A combination  Find

a NIM of a student from 500 entries (random) .