Teknik Informasi

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

© Budi Hartono, ST, MPM

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

B

t1

Algorithm Exchange_the_contents

t1 : A contains blue, B contains yellow © Budi Hartono, ST, MPM

Steps of problem solving using computers  Problem

Identification  Problem Analysis  Algorithm Design  Computer programming (coding)  Testing (debuging)  Documentation

© Budi Hartono, ST, MPM

problem solving phase

implementation phase

Steps of problem solving using computers (2)  Problem  find

Identification

the real needs of customers

 Problem

Analysis

 Elaborate

further problems.  Generate alternative solutions.  Compare and find the optimum strategy.

© Budi Hartono, ST, MPM

Steps of problem solving using computers (3)  Algorithm

design

Define the solution idea > example: optimization  linear programming, non-linear programming, forward induction, backward induction, etc > global  Develop

Algorithm  Validate Algorithm > represent the solution?  Analysis

Algorithm

> efficiency © Budi Hartono, ST, MPM

Good Algorithms … 1. 2. 3. 4. 5.

The procedure is logic and easy to understand The validity is traceable Not ambiguous Easily transferable to computer program Independent to any programming language © Budi Hartono, ST, MPM

Steps of problem solving using computers (4)  Coding  converting  it

/ translating

should:

 integrated  logics  efficiency

in the usage of time & memory

 flexibility  simplicity

© Budi Hartono, ST, MPM

Steps of problem solving using computers (5)  Debugging  does

it run well ?  syntax error?  logical error?  memory usage error?  etc …  Documentation  user

manual  future development © Budi Hartono, ST, MPM

Presenting Algoritms Pseudocode

1. -

2.

description

Flowchart - graphical representation

© Budi Hartono, ST, MPM

Pseudocode  descriptive  using

similar language  programming

will be discussed later …

© Budi Hartono, ST, MPM

Flowchart  Graphical

representation of the algorithms  Easy to use; easy to check  Independent to any programming language

© Budi Hartono, ST, MPM

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

© Budi Hartono, ST, MPM

Pass k = 1 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

© Budi Hartono, ST, MPM

Result, min = 2

Pass k = 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

© Budi Hartono, ST, MPM

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 © Budi Hartono, ST, MPM

START

k=1

k = k+1

1. Find min

2. Position min @ k

K=4 ? YES © Budi Hartono, STOPST, MPM

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

© Budi Hartono, ST, MPM

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)

© Budi Hartono, ST, MPM

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 min  data#j {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)

© Budi Hartono, ST, MPM

I leave the flowchart for the next week’s homework

© Budi Hartono, ST, MPM

Basic Structures of Algorithms  Sequence  Selection  Repetition

© Budi Hartono, ST, MPM

Basic Structures of Algorithms

A1

Sequence

A1

A2

A3

A3

A2

A4

A4

THE RESULT ?

A

© Budi Hartono, ST, MPM

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

© Budi Hartono, ST, MPM

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 … © Budi Hartono, ST, MPM

Basic Structures of Algorithms

Selection

 Another

structure If condition then action 1

else action 2  indenting  Your

example … © Budi Hartono, ST, MPM

Basic Structures of Algorithms

 An

Repetition

advantage of using compie:

 Do

repetitive jobs without getting bored  Precision I

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

© Budi Hartono, ST, MPM

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.

??? © Budi Hartono, ST, MPM

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 © Budi Hartono, ST, MPM

Basic Structures of Algorithms

 General

Repetition

Structure

Repeat action Until condition

© Budi Hartono, ST, MPM

A combination  Find

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

© Budi Hartono, ST, MPM