ICS week 8b
of 17
/17
Embed Size (px)
Transcript of 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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 2/17
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.
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 3/17
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.
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 4/17
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 5/17
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 6/1722 November 2011 Birkbeck College, U. London 6
Program 2 for XOR
Input: binary digits a,bOutput: a XOR b
1. If a==b Return 02. Else Return 1
3. Halt
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 7/1722 November 2011 Birkbeck College, U. London 7
Program 3 for XOR
Input: binary digits a,bOutput: a XOR b
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 8/17
8/3/2019 ICS week 8b
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
8/3/2019 ICS week 8b
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 11/1722 November 2011 Brookshear section 5.2 11
Pseudo Code: repeated execution
General formwhile (condition) do (activity)
Example
while (tickets remain) do (sell a ticket)
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 12/1722 November 2011 Brookshear section 5.2 12
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)
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 13/17
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 14/17
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
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 15/17
22 November 2011 Brookshear Section 5.2 15
Pseudo Code: procedures
General typeprocedure name
Examples
procedure helloWorld //no parametersprocedure sort (List) // parameter List
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 16/17
22 November 2011 Brookshear Section 5.2 16
Pseudo Code: alternatives to brackets
procedure name (activity)
endProcedure
while (condition)
do (activity) endDo
endWhile
8/3/2019 ICS week 8b
http://slidepdf.com/reader/full/ics-week-8b 17/17
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
