ICS week 8b

8/3/2019 ICS week 8b

http://slidepdf.com/reader/full/ics-week-8b 1/17

22 November 2011 Birkbeck College, U. London 1

Introduction to Computer Systems

Lecturer: Steve Maybank

Department of Computer Science and Information [email protected]

Autumn 2011

Week 8b: Pseudo Code and Algorithms



22 November 2011 Brookshear section 5.1 2

Algorithms

Definition: an algorithm is an orderedset of unambiguous, executable stepsthat defines a terminating process.

The steps are often called instructions.

Termination is by a special instruction:

halt.



22 November 2011 Brookshear sections 5.1 and 5.2 3

Terminology

Programming language: system forrepresenting algorithms in a human readableform suitable for conversion to machine code.

Program: representation of an algorithm in aprogramming language.

Pseudo code: system for the informal

representation of algorithms. Hardware: device to carry out the steps or

instructions in a program.



22 November 2011 Brookshear Section 5.1 4

Representation of an Algorithm

The same algorithm can be represented inmany different ways:

F = (9/5)C+32 F <- (9*C)/5+32

To obtain F multiply C by (9/5) and then add32.

Lookup table for Fahrenheit and Centigrade



22 November 2011 Birkbeck College, U. London 5

Program 1 for XOR

Input: binary digits a,bOutput: a XOR b

If a==0 and b==0 Return 0 If a==0 and b==1 Return 1

If a==1 and b==0 Return 1 If a==1 and b==1 Return 0

Halt


http://slidepdf.com/reader/full/ics-week-8b 6/1722 November 2011 Birkbeck College, U. London 6

Program 2 for XOR


1. If a==b Return 02. Else Return 1

3. Halt


http://slidepdf.com/reader/full/ics-week-8b 7/1722 November 2011 Birkbeck College, U. London 7

Program 3 for XOR


1. Convert a to the integer ia2. Convert b to the integer ib

3. ic=remainder on dividing ia+ib by 24. Return ic

5. Halt


http://slidepdf.com/reader/full/ics-week-8b 9/1722 November 2011 Brookshear, Section 5.2 9

Pseudo Code: assignment

General formname <- expression

Examples

funds <- current + savingsx <- 10


http://slidepdf.com/reader/full/ics-week-8b 10/1722 November 2011 Brookshear section 5.2 10

Pseudo Code: conditional selection

General formif (condition) then (activity)

else (activity)

Exampleif (year is leap year)

then d <- total divided by 366

else d <- total divided by 365

Key or reserved words in bold



Pseudo Code: repeated execution

General formwhile (condition) do (activity)

Example

while (tickets remain) do (sell a ticket)



Pseudo Code: indentation

if (not raining)then (if (temperature = hot)

then (go swimming)

else (play golf))

else (watch television)

if (not raining) then (if (temperature=hot) then (goswimming) else (play golf)) else (watch television)



Procedure

Definition: set of instructions which canbe used as a single unit in differentcontexts.

A procedure call contains the name of the procedure and any data supplied to

the procedure A result calculated by the procedure can

be obtained using a return statement.22 November 2011 Brookshear, Section 5.2 13



Example of a Procedure

procedure temp(c)

f=(9/5)*c+32;

return f;

endProcedure

f1=temp(34)

22 November 2011 Birkbeck College 14

Definition of aprocedure

Procedure call




Pseudo Code: procedures

General typeprocedure name

Examples

procedure helloWorld //no parametersprocedure sort (List) // parameter List




Pseudo Code: alternatives to brackets

procedure name (activity)

endProcedure

while (condition)

do (activity) endDo

endWhile



Exercise

Write an algorithm in pseudo code tocarry out the following task:

input: a 1-dimensional array A of integers

output: the integer -1 if A[i]≥ A[i+1] for

0≤i≤Length[A]-2, otherwise the leastinteger j such that A[j]<A[j+1].

22 November 2011 Birkbeck College 17

ICS week 8b

Documents

Transcript of ICS week 8b