The Arab Open University OUBuild or Scratch Discussion

Faculty of Computer StudiesCourse Code: TM111
Course Title: Introduction to computing and information technology 1
Tutor Marked Assignment
Cut-Off Date: TBA
Total Marks: 15
Plagiarism Warning:
As per AOU rules and regulations, all students are required to submit their own TMA work and
avoid plagiarism. The AOU has implemented sophisticated techniques for plagiarism detection.
You must provide all references in case you use and quote another person’s work in your TMA.
You will be penalized for any act of plagiarism as per the AOU’s rules and regulations.
Declaration of No Plagiarism by Student (to be signed and submitted by student with TMA
work):
I hereby declare that this submitted TMA work is a result of my own efforts and I have not
plagiarized any other person’s work. I have provided all references of information that I have
used and quoted in my TMA work.
Important Note:
•
•
For all questions you need to write the full algorithm and implement the algorithm
by using OUBILD script. The student should provide provide one screenshot for
the OUBUILD script and two screenshots for differnt outputs.
If you will not provide SCREENSHOTs you will lose grades
Name of Student:
Signature:
Date:
Question 1 : (8 marks)
On one day a year a programming club at AOU hosts a tournament. Each entrant is
recorded in the appropriate tournament category on arrival and is registered a
corresponding level. Participants in level one will be entered in the basic training and
competition; participant in level two and three will be entered in the intermediate training
and competition; those in level 4 will be entered in the junior competition.
1- You are required to write an algorithm which is required to decide the appropriate
category for the entrant; Display the entrant’s in a list for that category and output
the corresponding level. Hint[The tutor will keep registering the students
until he pressed -1 to stop and exit from the loop ]
2- Draw the flowchart for the above algorithm
3- Build your algorithm by OUbuild and provide screenshots for the output?
Question 2: (5 marks)
Ahmad wanted an algorithm to list her favourite games. He wanted to be able to enter a
favourite game to be added to the list. He did not want duplicated on the final list but did
want to be told, having entered proposed game, either that it was a duplicate or that had
been added to the list. Or he can enter the list of favourites and then the algorithm will
delete the duplicated one.
1- You are required to write an algorithm to do the above task?
2- Build your algorithm by OUBUILD and then provide screenshots showing that he
has entered games twice and not added to the list. Ahmad will keep add his
favourite game until he press -1 to exit from the loop.
Question 3: (2 marks)
Consider a four-hour film to be displayed on a computer at 24 fps. Each frame is 420 x
270 pixels and a 24-bit RGB color encoding is being used
a- How many bytes will be required to represent the whole film?
b- In how many gigabytes the film in (a.) can be represented?
Good luck
End of the question
Digital Media and HCI
AOU UNIVERSITY
Introduction
2
 The term digital media includes both the tools we use to create
media such as text, images, audio and video, and also the idea of
communicating and sharing through the internet and the web.
 Technologies have developed the production and distribution of
digital media content as well as its consumption.
 Whether in an educational or training context or in a work-based
setting, the use of audio and video offers a richer and more
interactive environment for educators or other presenters to express
messages.
 Most material on the web can be grabbed, copied and modified but
this is often illegal.
 Privacy and copyright/IPR (intellectual property rights) are, indeed,
areas of great ethical and legal concern.
Representing the real world in digital form
3
 There are two major ways of representing information from the real
world.
1. Analogue representation
2. Digital representation
 We live in an analogue world with an infinite range of sounds, colors,
touches, tastes and smells that we can perceive through our senses.
 In analogue representations, the representation is equivalent of the
real-world aspect that we are trying to capture.
 Example: Temperature is analogue and
can take on any value within a given range.
 When temperature is measured by a
traditional mercury- or alcohol-in-glass
thermometer, we have a continuous,
analogue representation (Figure 1).
Figure 1
Representing the real world in digital form
4
 Another way to measure temperature is by using a digital
thermometer where a sensor is used to convert the temperature
into an electrical voltage (Figure 2).
 At this stage, the representation is an analogue voltage but an
electronic circuit converts the analogue voltage into a digital
representation, as a numerical value of degrees Celsius or
Fahrenheit.
 This means that the values are converted into discrete values.
 A discrete value is something that can be counted, whereas
continuous data is measured.
 One example of a discrete quantity is the
number of people in a room; people are
counted in whole numbers: one person, two
people, etc.
Figure 2
Representing the real world in digital form
5
 Figure 3 shows two temperature plots on the same axes: one a plot of a
continuously varying temperature, and the other the corresponding series
of discrete values that might come from a digital thermometer.
Figure 3
Representing the real world in digital form
6
 Which items in the following list are fundamentally
analogue and which fundamentally discrete?
1. The amount of heat from a fire. Analogue
2. The energy of a star. Analogue
3. The pressure of the atmosphere. Analogue
Digital
4. The price of petrol.
5. The size of the audience at a play.
Digital
6. The speed of a car. Analogue
Representation
7

Representations play a central role in facilitating
communication by establishing a relationship
between some perceptible form (or symbol) and an
associated meaning (or content) subject to some
convention.



Crosses on churches, or crescents on mosques indicate places
of worship (‫)أماكن عبادة‬, and are intended to be seen.
Bleeps at pedestrian crossings (‫ )معابرالمشاة‬indicate the light is
green, and are intended to be heard.
To be effective in communication, a representation
must meet at least the following conditions:


The form of the representation must be perceivable in some
way;
The relationship between form and content(meaning) is
shared by all parties involved in the communication process.
Properties of Representations
8

Humans have many different ways of perceiving
representations, which are also used in our
communication with computers.
1.
Auditory representations are perceived as sound.


2.
Visual representations are perceived as sight.


3.
Human use music and spoken language.
Computers use alarms and beeps to attract human attention.
Humans use written music and language, traffic signs, flags,
and paintings.
Computers use scanners to ‘see’ images and the screen to
communicate visual images.
Tactile representations are perceived by touch.


Humans with visual and hearing impairments use various
languages that rely on touch as the case with Braille language.
Computers use keyboards, joysticks, vibrating i-mice, ….
Properties of Representations
9
 Almost any analogue quantity can be represented
digitally.
 This means that the representation can be stored
and manipulated by a computer, with the values of
the digital representation being ‘coded’ as binary
numbers that can be stored.
 We will now discuss how digital codes are used to
represent images and sounds.
Representing images
10
 On a computer screen, images are generated by dividing the display
into a large number of tiny units called pixels.
 Each pixel can be displayed in a number of different colors and levels
of light intensities or brightness.
 The greater the number of pixels used for a given size of display, the
more detail can be displayed and the higher the quality of the image.
 To begin with, we’ll look at
the representation of black
and white images.
 Let’s consider an artificially
small-scale
example:
a
display using eight rows of
sixteen pixels displaying a
triangle (Figure 4).
Figure 4
Representing images
11
 If we represent a white pixel by a binary 0, and a black pixel
by a 1, we can code the image and convert it into a set of
binary 1s and 0s that we could store or transmit (Figure 5).
 The display system described so far is simple, but quite
restricted.
 By increasing the number of pixels,
we can improve the amount of
detail the image contains (i.e. its
resolution) and get high-quality,
black and white images.
 This sort of encoding is referred to as a
Bitmap or Raster Graphics.
Figure 5
Representing images
12
Instead of using just one bit, if we use two
bits for each color. In this case we have
four possible codes representing four
colors (Figures 6 and 7):
00 white
01 red
10 blue
11 black
 Binary coding can be extended to
represent an increasing range of colors.
 For eight colors we need to need 3 bits
binary word (23 = 8).
 To represent 16 different colors we need
4 bits binary word (24 = 16).
Figure 6
Figure 7
Representing images
13
 A set of a given number of bits used for data representation
is called a binary word.
 An n-bit binary word can represent 2n different options.
 Example: To code 300 colors we need 9 bits word length.
 8 bits are not enough! 28 = 256
 Any coding scheme that allocates a binary code to each pixel
in order to define its color and brightness is called a
bitmap.
 File formats are agreed-upon, standardized ways of
organizing and storing the binary data that represents an
image in your computer.
Representing images
14
 Because bitmap files are relatively large, they’re not
the most appropriate choice of format for images to
be viewed on the web.
 Other techniques such as JPEG use information
about human perception to reduce file sizes.
 They still assign binary codes to pixels, but in a
different way, and are not usually called ‘bitmaps’.
 Vector graphics: is a coding image technique,
instead of sending or storing information about each
pixel, information about the different shapes in the
image is used.
Representing images
15
 Vector graphics are most appropriate where the image is
made up of regular shapes, as in many Web or computer
game graphics, examples:
 A straight line can be defined by its starting and end points.
 A circle by its center and radius.
 In this way, file sizes can be kept much smaller than a
bitmap, provided the complete graphic consists only of the
shapes allowed within the vector graphic system.
 It is also easy to produce simple animations of such shapes.
 For images such as photographs or motion pictures the
vector graphics approach is not effective.
Real-world implications
16
 Computer’s memory and hard drive is measured in:
 bytes = 8 bits
 kilobytes (KB) = 1024 or 210 bytes
 megabytes (MB) = 1024 KB = 220 bytes
 gigabytes (GB) = 1024 MB = 230 bytes
 Question1: A smartphone has a screen resolution of 640 ×
960 pixels. How much data (in bits, bytes and MB) is
required to display an image, if it use 16 bits for each pixel.
 Answer: 640 × 960 = 614400 pixels in total
16 × 614400 = 9830400 bits
9830 400 ÷ 8 = 1 228800 bytes
1 228800 ÷ 220 = 1.17 MB
Real-world implications
17
Question2: Consider an image of size 100 x 240. How many bits and bytes are
required to store this image inside the computer
a. Using only 2 colors: black and white.
b. Using 3 bits per pixel in grayscale model.
c. Using RGB model.
Answer:
The number of pixels in this image is 100 x 240 =24000 pixels.
a. For black and white images, only 1 bit is used to represent a pixel.
The number of bits needed to represent this image = 24000 * 1 = 24000 bits
The required number of bytes = 24000 / 8 = 3000 bytes.
b. Here, 3 bits are used to represent a pixel.
The number of bits needed to represent this image = 24000 * 3 = 72000 bits
The required number of bytes = 72000 / 8 = 9000 bytes.
c. For RGB model, 24 bits are used to represent a pixel.
The number of bits needed to represent this image = 24000 * 24 = 576000 bits
The required number of bytes = 576000 / 8 = 72000 bytes.
Real-world implications
18
Question3: A file in bitmap format is 3 MB in size, how long will it
take to download the file from the internet if my internet connection
is running at 14.1 Mbs?
Before solving the question, you need to note that:
– The file is 3 megabytes, while the internet speed is 14.1 megabits
per second.
– In order to calculate the time taken to download the file, we must
first convert the values to bits.
Answer:
– The file size is 3 × 1024 × 1024 × 8 = 25 165 824 bits.
– The internet speed is 14.1 × 1000 × 1000 = 14 100 000.
– Using the formula time = size ÷ speed
– time = 25 165 824 ÷ 14 100 000 = 1.78 seconds
Real-world implications
19
Question4: A common bitmap format for displaying reasonably highquality digital images is to use 24 bits for each pixel.
(a) How many pixels are required for 1024 × 768 screen resolution?
How many bits of data does this require for each image?
(b) My internet connection provides an upload speed of 2.3 Mbs. How long
will it take to upload such an image?
Answer:
(a) The display is 1024 × 768 pixels = 786432 pixels.
Each pixel uses 24 bits, so the total number of bits required is:
786432 × 24 = 18874368 bits.
(b) The upload speed is 2.3 Mbps, so we convert this value to bits:
2.3 × 1000 × 1000 = 2300000 bits.
Using time = size/speed:
18874368 / 2300000 = 8.21 seconds (rounded to 2 decimal places).
Representing Videos
20
 A Video or a movie, is a series of images (frames) that
slightly differ one from another, passing them one after the
other at a certain speed (frame rate) will give the illusion of
movement.
 Frame rate is the speed of flipping the frames one after
the other.
 Films are usually shot and displayed at 24 frames a second (fps).
 TV pictures are presented at between 25 and 30 fps, depending on
what country you live in.
 High definition TV, currently only available in Japan, uses 60 fps.
Representing Videos
21
Question: Consider a two-hour film to be displayed on a computer
at 24 fps. Each frame is 640 x 380 pixels and a 24-bit RGB color
encoding is being used. How many bytes will be required to
represent the whole film?
Answer:
The number of pixels in one frame = 640 * 380 = 243200 pixels.
 The number of bytes needed to represent one frame = 243200 * 3 = 729600
bytes.
 The number of seconds in 2 hours = 2 * 60 * 60 = 7200 seconds.
 The number of frames in 2 hours = 7200 * 24 = 172800 frames.
 The number of bytes needed to represent the whole film = 172800 * 729600
= 126074880000 bytes.
= 126074880000 / 230 = 117.416 GB.

Sound
22
 Audacity is sound editing program to record and manipulate sound (Figure 8).
 It is available for computers using Windows, Macintosh operating system or
Linux operating systems.
 The program allows you to load, record, save and play sound using different file
formats, to look at the waveform of sounds and to edit sounds.
Figure 8
Sound
23
 Sound is another analogue feature of the world.
 If you shout, hit a piano key or drop a plate, then you set
particles of air vibrating and your ears will interpret this
vibration as sound.
 The sounds we hear generally consist of small rapid
movements of the atmospheric air pressure that surrounds us.
 Vibrating a tuning fork makes pure sound that makes particles
of air move backwards and forwards with the fork.
 One way to visualize this movement is to draw a graph of how
far an air particle moves backwards and forwards as time
passes.
 The graph of a typical waveform is shown Figure 9.
Sound waves
24
 A cycle represents the time between adjacent peaks (or troughs), and the
number of cycles completed in a fixed time (usually a second) is known as
the frequency.
 The amplitude of the wave (i.e. maximum displacement) determines
how loud the sound is.
 The frequency decides
how low- or highpitched the note sounds
to us.
 Note that Figure 9 is
theoretical; in reality,
the
amplitude
will
decrease as the sound
fades away.
Figure 9
Sound Waves
25
 A tuning fork is a very simple instrument, and so makes a pure sound.
 Real instruments and real noises are much more complicated than this.
 An instrument like a clarinet would have a complex waveform (Figure 10).
 A dropped plate would have irregular waveform (Figure 11).
Figure 10
Figure 11
Sound Sampling and Storing
26
 A microphone is used to convert the sound pressure wave into an
analogue electrical signal.
 This electrical signal needs to be converted (coded) into a digital
representation.
 The process of digitizing a sound includes two stages: Sampling and
Quantization.
 As we split up images by dividing them into pixels, we can split a sound
wave up by dividing it into very small time intervals called samples.
 The first stage of the process is to measure the amplitude of the sound
wave at regular time intervals. Taking readings like this is called
sampling.
 The number of times per second we take a sample is called the
sampling rate.
 We will take the tuning fork example, set an interval of 0.5 seconds and
look at the state of the wave every 0.5 seconds, as shown in Figure 12.
Sound Sampling and Storing
27
 Reading off the amplitude of the wave
at every sampling point gives the
following set of numbers:
+9.3, −3.1, −4.1, +8.2, −10.0, +4.0, +4.5
 If we plot a new graph of the waveform,
using just these numbers, we get the
graph in Figure (13).
 The plateaux at every sampling point
represent the intervals between
samples,
where
we
have
no
information, and so assume that
nothing happens.
 This means that the audio signal
produced by the sample does not
closely follow the original signal,
leading to poor-quality sound.
Figure 12
Figure 13
Sound Sampling and Storing
28
 How can we improve sound quality? By making our sampling interval
smaller, that is, we can decrease the temporal splitting up of the
waveform.
 Figure 14 shows sampling a sound wave at intervals of 0.1 seconds.
 Figure 15 shows the digital conversion of Figure 14.
Figure 14
Figure 15
Sound Sampling and Storing
29
 Quantization is the second stage.
 It is the process of converting each sample into a suitable number for computer
storage by dividing the maximum voltage range of the analogue sound signal into
a number of discrete voltage bands.
 The result is a string of numbers at regular intervals, as shown in Figure 16.
Figure 16
Sound Sampling and Storing
30
 If we want to just send sound somewhere, then we can simply send the string of
numbers along a suitable transmission channel to a digital-to-analogue
converter and loudspeaker at the other end.
 Any device that can store large quantities of numbers can be used to store sound;
such as modern music players, your phone’s internal memory and any devices that
contain a standard hard drive.
Question: For a 4 seconds of single-channel storage, suppose that each
sound sample requires 2 bytes of storage, and that an additional 44
bytes are needed for format information about the sound. If the
sampling rate is 44100 samples per second, what is the size of the file
you would expect ?
Answer:
– The sound in the file is 4 seconds long. The sampling rate is 44 100 samples/sec.
– The sampling rate = 44 100 X 4 = 176400 samples.
– If each sample requires 2 bytes of storage, and an additional 44 bytes are needed for format
information, then:
– the file size should be (176400 × 2) + 44 = 352844 bytes.
Compression of digital files
31
 The digital encoding of sound, images and, especially, video produces
large data files.
 For example: 500-pages text document created in plain-text format in
Microsoft Word is 1.8 MB whereas a simple 30-second-long video may be
186 MB.
 Compression means taking the original digital file and converting it into
a new file that uses considerably fewer bits without significantly
degrading (corrupting) the quality of the original content.

This results in saving the memory needed to store the data and increasing the speed of transfer.
 The ratio between the uncompressed file size and compressed file size is
known as the compression ratio.
C𝑜𝑚𝑝𝑟𝑒𝑠𝑠𝑖𝑜𝑛 𝑟𝑎𝑡𝑖𝑜 =
𝑠𝑖𝑧𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑢𝑛𝑐𝑜𝑚𝑝𝑟𝑒𝑠𝑠𝑒𝑑 𝑓𝑖𝑙𝑒 (𝑜𝑟𝑖𝑔𝑖𝑛𝑎𝑙 𝑓𝑖𝑙𝑒)
𝑠𝑖𝑧𝑒 𝑜𝑓 𝑡ℎ𝑒 𝑐𝑜𝑚𝑝𝑟𝑒𝑠𝑠𝑒𝑑 𝑓𝑖𝑙𝑒
Compression of digital files
32
 The higher the compression ratio is, the less storage space would
be needed for the resulting compressed file.
 If a 10 MB file is compressed to 2 MB, the compression ratio is 10:2,
which is equivalent to 5:1
 If the same file is compressed to 5 MB, the compression ratio is 10:5
which is equivalent to 2:1.
 Two main types of compression:
 Lossless compression techniques do not lose any significant aspect
of the original representation.
 Lossy compression loses parts of the original in a controlled way.
 Decompression is the reverse operation, where the redundant
parts are put back into the representation to restore it to its initial
form.
Lossless compression
33
 Lossless
compression, the digital data is stored in a
compressed form such that it can be recovered, sample for
sample, with nothing altered or lost.
 A computer ZIP file (created using the popular Winzip
compression software) is an example of lossless compression of
digital data
 A powerful form of lossless coding is called dictionary-based
coding.
 In most digital files, some data is repeated over and over again.
 A compression algorithm simply gets rid of this redundancy by
scanning for patterns, and translating those patterns into
something that takes up less space.
Lossless compression
34
We will use the following text to demonstrate how dictionary-based coding
compression works:
When the going gets tough, the tough get going.
–
–
–
there are 9 words, 8 spaces and 2 punctuation symbols: a total of 47 characters.
If one unit of memory is allocated for each character, the file will consist of 47
units.
‘the’, ‘going’ and ‘tough’, are repeated.
Our ‘dictionary’ of words looks like this:
1 the
2 going
3 tough
The sentence can now be expressed as:
When 1 2 gets 3, 1 3 get 2.
–
Thus, the original sentence uses 47 units of memory while the compressed
version uses only 27.
Lossless compression
35
 Another technique for lossless compression is called run-
length encoding.
 In this compression method, ‘runs’ of similar data items are
recognized and replaced with a single instance of the data
item, together with a number indicating how many times the
item is repeated.
 Example 1: the striped pattern in Figure 17 can be
represented by the binary sequence 01010101010101. The
sequence repeats 01 seven times. This can be represented in
run-length encoding as: 7(01).
Figure 17
Lossless compression
36
 Example 2: the pattern in Figure 18 can be represented by the
binary string:
1111111111111111111111111111111111111111111111111111111111111111111111
1111111111000000000000000000000000000011111111111111111111
The sequence has 80 ones, 28 zeros
and 20 ones.
This can be represented in runlength encoding as: 80(1)28(0)20(1)
Figure 18
 Lossless coding is used in a similar way for simple images, such as
line drawings and simple shapes in the GIF (Graphics Interchange
Format) format used for images on websites.
Lossy compression
37
 In lossy compression, the original file is processed in a way that
preserves the important information, but discards other
information that is less important for the particular application
(such as Joint Photographic Experts Group JPEG)
 Lossy compression of audio, image and video files exploits
features of human perception to reduce the amount of data
needed.
 Psychoacoustics is the study of how humans perceive and
respond to sound.
 Knowledge from psychoacoustics is used in lossy compression
techniques to reduce the amount of information a sound signal
contains without affecting the perceived sound.
 MP3 audio compression offers acceptable audio quality with a
high compression ratio in the region of 11:1 (read ‘eleven to one’).
Digital image compression
38
 As described before, a digital image is made up of multiple small
elements known as pixels.
 The more pixels there, the higher is its resolution, but the greater is the
memory space required .
 There are two solutions to reduce the amount of memory required:
1.
2.
Reduce the number of pixels required (therefore reducing image resolution).
Compress the data using compression software.
 One of the most important standards for photo image coding (also used
as part of MPEG video) is the one produced by JPEG (file extension
jpg).
 This compression technique divides a picture up into small blocks of
pixels and performs complex calculations to arrive at a concise
description of the block. Remove or reduce some components because
they’re not important for human vision.
Number systems
39
We have different number systems:
 Decimal (Base 10)
 It uses 10 symbols (0, 1, 2, 3, 4, 5, 6, 7, 8 and 9).
 Binary (Base 2)
 It uses 2 symbols (0 and1).
 Octal (Base 8)
 It uses 8 symbols (0, 1, 2, 3, 4, 5, 6 and 7).
 Hexadecimal (Base 16)
 It uses 16 symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D,
E and F).
Number systems
40
 Decimal (Base 10) System
 The system that is used worldwide.
 It uses ten digits (0 to 9) and each column counts
groups ten times bigger than those counted in the
column to its right.
 Examples:
 37 = 7 + 3*101
 345 = 5 + 4*101 + 3*102
 4621 = 1 + 2*101 + 6*102 + 4*103
Number systems
41
 Octal (Base 8) System
 The system that is mostly used by computer scientist.
 It uses eight digits (0 to 7) and each column counts
groups eight times bigger than those counted in the
column to its right.
 Examples:
 468 = 6 + 4*81 = 3810
 1258 = 5 + 2*81 + 1*82 = 8510
Number systems
42
 Binary (Base 2) System
 The system that is used by the computer.
 It uses two digits (0 and 1) and each column counts
groups two times bigger than those counted in the
column to its right.
 Examples:
 1102 = 0 + 1*21 + 1*22 = 610
 11012 = 1 + 0*21 + 1*22 + 1*23 = 1310
Number systems
43
 A bit is short for binary digit and refers to a 1 or a 0 stored in the computer.
 A byte is a group of eight bits that can be used to represent numbers between 0
and 255. A byte looks like this:
 The largest number we can store in the a byte is 11111111 = (255)10.
 The smallest number we can store in the a byte is 00000000 = (0)10.
 The word size for a computer is the number of bits that the CPU of a particular
computer can handle at one time.
 When the word size of a computer is 32 bits (4 bytes), the largest binary number
that the computer can process in a single operation would be
11111111111111111111111111111111 which is decimal 4,294,967,295.
Binary to Decimal
44
 To convert from binary to decimal a method known as Positional notation
can be used. The below figures illustrate the method with an example of how
to convert 100110112 to decimal.
Octal to Decimal
45
 To convert from octal to decimal the following formula can be used:
Decimal Form = Ʃ(ai x 8i)
 Where, ‘a’ is the individual digit being converted, while ‘i’ is the number of the
digit counting from the right-most digit in the number, starting with 0.
 Here are two examples:
Decimal to Binary
46
 One of the easy methods used to convert from decimal to binary is
comparison with descending powers of two and subtraction.
 Converting the decimal number 15610 to binary is shown below:
Decimal to Octal
47
 The conversion of a decimal number to its octal equivalent is done by
the repeated division method. You simply divide the base 10 number by 8
and extract the remainders.
 Here are two examples to illustrate this method:
Interacting with Computers (HCI)
48
Human–computer interaction (HCI)
 HCI is the study of how humans interact with computers
and their applications.
 HCI looks at the design of computer systems in which
humans and computers need to work together and tells
us how to build user interfaces that are safe, efficient,
easy and enjoyable to use (as well as functional).
 HCI is a broad subject covering all aspects of the way in
which people interact with computers and so draws on
ideas from many subjects, including computer science,
psychology,
engineering,
artificial
intelligence,
philosophy, sociology, anthropology and graphic design.
Interacting with Computers (HCI)
49
The importance of good user interface design
 A good UI is:
 One that is easy to use and easy to understand;
 One that meets the needs of the intended users;
 One
that supports users in the tasks they wish to
undertake.
 A good UI designer thinks about the users of the UI
and pays great attention to the usability of the UI
for users.
 A cardinal rule for good UI design is always to
be aware of a user’s needs.
User Interface Essentials
50
User interface design principles
 There are several UI design principles in the HCI
literature.
 The best known are those applying to visibility,
feedback, affordance, simplicity, structure,
consistency and tolerance of UI designs.
 Each design principle has helpful guidelines
associated with it and their application is described
by means of examples.
User Interface Essentials
51
Visibility
 Visibility in the context of UI design means making it clear what a
UI element is used for.
 All UI elements should have good visibility.
 This can be dine by good labeling (text or image).
 Examples:
 In
a UI for DVD player, standard recognizable symbols are used
(Figure 19).
 Buttons have labels to make their purpose clear for users (Figure 20).
Figure 19
Figure 20
User Interface Essentials
52
Feedback
 Feedback in the context of UI design means making it clear what action has been
achieved through the use of the UI element.
 Feedback is used to say that one part of an action has finished and another can
begin.
 Feedback can be visual, audible or tactile.
 Examples:


When pressing any key of a mobile phone, a beep is heard.
When pressing a button on a UI, the button is darkened.
Affordance
 Affordance in the context of UI design means making it clear how a UI element
should be used.
 At a very simple level, to afford means ‘to give a clue’ of how to interact.
 Examples:


In Windows OS, buttons are given a shadow which affords pushing.
The underlining of links on web pages affords clicking.
User Interface Essentials
53
Simplicity
 Simplicity means keeping things as simple as possible.
 To achieve simplicity, employ actions, icons, words and user interface
controls that are natural for the user.
 Examples:
Use simple language.
 Break complex tasks into simpler subtasks.
 Find out what tasks are most common for your users and make these as short
and simple as possible for the user to achieve.

Tolerance
 Tolerance refers to the ability of a UI to prevent errors if possible, or to
make them easy to recover from, if not.
 Examples:
To prevent the wrong choice of menu item, some items might be grayed out.
 Before deleting a file, a confirm message is displayed.

User Interface Essentials
54
Structure
 A UI needs to be structured in way that is meaningful and useful to user.
 It is important to structure the UI in a way that will be meaningful for the user.
 Example: In MS Word UI, related commands are grouped together (Figure 21).
Consistency
 Consistency in appearance, positioning and behavior within the UI makes a
system easy to learn and remember.
 Example: Icons in the top bar of different MS Office applications are the same
and function in a similar way (Check Figure 22 and compare it with Figure 21).
Figure 21
Figure 22
Block 2 Part 6
ALGORITHMS
AOU UNIVERSITY
Introduction
2
 It is not uncommon to read articles with titles like
‘Google’s algorithm for ranking web pages’ or
‘Facebook’s algorithm for curating news stories’.
 Our civilization is increasingly reliant on algorithms,
therefore it’s worth learning more about exactly what
they are, and about some of their strengths and
weaknesses.
 You have learned that an algorithm may describe
how a problem can be solved by a computer.
 However, as we discuss in this part, the concept of an
algorithm is more general than that.
Introduction
3
 An algorithm simply is a ‘step-by-step guide to completing a particular
task’.
 Many of our everyday activities follow an underlying algorithm.
 For example, here is an algorithm for brushing teeth:
Introduction
4
 Recipes are
obviously algorithmic, such as this one for
making a beetroot cake:
The fundamentals of algorithms
5
 A well-written algorithm for a program can be
implemented (written) in a variety of
programming languages.
 The implementations of an algorithm in different
languages of course all look different, but they all
share the fundamental features described by the
algorithm.
 Understanding these fundamental algorithmic
features can help you more readily understand
programs even in languages that are new to you.
Algorithm Definitions
6
 An algorithm is: a set of step-by-step instructions to
complete a particular task.
 Similarities between everyday algorithms and those
used for programs?
Both have set of instructions (the style of instruction in
each case is very different).
2. Both complete in a finite amount of time.
1.
–
Note: There are processes that go on indefinitely, but we don’t
consider them amongst the algorithms we analyze in this part.
Just like a recipe, an algorithm must stop. It need not be quick, it
may take years to generate an answer, but it must eventually
finish.
Algorithm Definitions
7
 Differences between everyday algorithms and those
used for programs?
Everyday algorithms are imprecise and might omit an
instruction relying of humans previous experience or
general knowledge. For example, a recipe might say
‘Bake for 45 mins at 180 °C’ without giving explicit
instruction to turn the oven on and off.
2. Algorithms for programs must be precise and selfcontained. They must contain all the instructions
required to solve the problem, and those instructions
must be unambiguous because computers cannot deal
with omission or imprecision.
1.
Algorithm Definitions
8
 In implementing their own algorithm, a programmer
might clarify the ambiguous and fill in missing steps,
and thereby arrive at a working program.
 One advantage of algorithms is that once an algorithm
is written down, it can often be reused over and over by
other people wanting to solve the same problem in
different programming languages.
 Algorithm can now be defined more precisely as:
A set of unambiguous, self-contained, step-by-step
instructions guaranteed to complete a particular task
in a finite amount of time.
Refinement
9
 Ambiguity is a real problem for algorithms designed for programs.
 Ambiguity can be overcome by breaking instructions down into
smaller steps to clarify the order of individual actions.
 This process is sometimes called refinement or decomposition.
 For example, we might start with an instruction:
Deduct rounded discount amount from total price.
 Then we might refine this as:
Calculate discount as 20% of total price
Round discount
Reduce total price by discount
Fundamental features
10
 Computer programs vary in purpose and complexity, as well as in the
languages they are written in. Consider these examples:
Google search engine
 camera face-detection software
 aircraft flight-control software
 online UK income-tax calculator

 The many tasks each of these programs perform are based on algorithms
that is, they follow precise, finite, step-by-step instructions.
 The algorithms for these and all other computer programs are built around
four simple ideas:
Inputs and outputs
 Sequences of instructions
 Repetition of instructions
 Selection of instructions.

 By combining these four ideas in different way, we can create an algorithm.
Inputs and outputs
11
 It’s possible to imagine someone writing an algorithm that takes no
external input and that always produces the same output.
 But, as a rule, an algorithm that always produced the same output would
be of little use.
 We want algorithms to be able to start with different data, inputs, and
produce output that varies according to the input data.
 This enables algorithms to be general-purpose problem-solving tools,
providing different solutions in different situations.
 For example, consider the following algorithm snippet which requires
two pieces of input data from the user and outputs one piece of data:
Input the first number
Input the second number
Display the mean (average) of the two numbers
Inputs and outputs
12
 In OUBuild, we might implement this as in Figure 1.
Figure 1
 Implementing the above algorithm In Python follows the same basic pattern:
number1 = input(‘Enter your first number ‘)
number2 = input(‘Enter your second number ‘)
mean = (float(number1) + float(number2)) / 2
print(‘Mean is’, mean)
Inputs and outputs
13
 Not all input data for an algorithm comes from the user.
 Some data that an algorithm needs might come from the
environment in which the program runs.
 For example, consider the following simple algorithm snippet:
Tell the user what last year was
 In OUBuild, as with many other languages, there is in-built data
providing the current date and time, etc. This sort of data can be
used by an algorithm, as follows:
Get this year
Subtract 1
Display last year
Sequence, repetition, selection
14
 Suppose a Cola merchant is giving loyalty points for their customers
according to the following algorithm:
Repeat (6) times
Input box price
Add box price to total price
If total price is greater than £ 5000 then
Calculate loyalty points as 5% of total price, rounded to nearest whole number
else
Tell the user the loyalty points earned
Tell the user no loyalty points earned
 The above instructions are followed in sequential order, from top to
bottom, except where an instruction involves repetition or selection.
Sequence, repetition, selection
15
 The algorithm starts with the repetition instruction:
Repeat (6) times
Input box price
Add box price to total price
 This instructs the algorithm to repeatedly iterate through the indented
sequence of actions, the loop body, in order, six times.
 The actions that are repeated are to:
Get the box price from the user
 Add the box price to the total price.

 The way the repetition instruction is set out within the algorithm, with the
condition at the top and the actions indented underneath, emphasizes the
connection between them.
Sequence, repetition, selection
16
 This particular sort of repetition instruction corresponds to a fixed
loop: one that repeats a sequence of actions a fixed number of times.
 In OUBuild, fixed loops are implemented with the block repeat[]{},
as in Figure 2.
 In Python, an equivalent code
can be implemented using
something known as a for loop
as follows:
total_price = 0
Figure 2
for item in range(6):
box_price = input(‘Enter box price ‘)
total_price = total_price + float(box_price)
Sequence, repetition, selection
17
 Python doesn’t have a direct equivalent of repeat_until{}.
 It has something called a while loop, which could be used to implement
the same algorithm as follows:
total_price = 0
box_count = 0
while box_count < 6: box_price = input('Enter box price ') total_price = total_price + float(box_price) box_count = box_count + 1  A while loop repeats while a particular condition holds. Here, the condition is: box_count < 6  Therefore, the while loop condition must be different from that needed for the OUBuild repeat_until{} loop, which repeats until its condition holds. Sequence, repetition, selection 18  Here is an algorithm for a program to count down from 100: Set i to l00 Repeat until ( i is less than 1 ) Tell the user the value of i Decrease i by 1 Tell the user ‘Blast off ! ’  Question: What change could be made to the condition in order to replace ‘Repeat until’ with ‘Repeat while’?  Answer1: Repeat while ( i is greater than or equal to 1 )  Answer2: Repeat while ( i is greater than 0 ) Sequence, repetition, selection 19  Back to our Cola merchant algorithm: after completing the repetition instruction the algorithm moves on to the following selection instruction: If total price is greater than £ 5000 then Calculate loyalty points as 5 % of total price rounded to nearest whole number Tell the user the loyalty points earned else Tell t he user no loyalty points earned  This is an ‘if … then … else’ selection instruction. Sequence, repetition, selection 20  This selection part starts by considering the condition: total price is greater     than £5000. If the condition holds, then the ‘if’ part (i.e. the first indented sequence of instructions) is carried out; and then the algorithm moves on below the selection instruction (and simply stops in this case). If the condition does not hold, the ‘else’ part is carried out (i.e. the second indented sequence of instructions); and then the algorithm moves on and stops. The way the algorithm is set out, with the condition at the top and the two sequences of instructions indented underneath, emphasises the connections between them. If it were not required to tell the user that no loyalty points were awarded when the total price is not greater than £5000, then the algorithm could have been written using a simpler ‘if’ instruction (without the ‘else’ part): If total price is greater than £ 5000 then Calculate loyalty points as 5 % of total price rounded to nearest whole number Tell the user the loyalty points earned Sequence, repetition, selection 21  In OUBuild, the selection part is implemented as in Figure 3. Figure 3 In Python, an equivalent code can be implemented using similar wording and indentations: if total_price > 50000:
loyalty_points = round(0.05 * total_price)
print(‘You have earned’, loyalty_points,’loyalty points’)
else:
print(‘No loyalty points earned’)
Sequential and nested selection
22
 Suppose I always provide for my
children the same meal on the
same day each week, as follows:
Monday – Meat loaf
 Tuesday – Shepherd’s pie
 Wednesday – Omelette
 Thursday – Chilli
 Friday – Fish and chips

 I
might create an algorithm
something like the following:
Input the day
If day is Monday t hen
Set meal t o ‘Meat loaf ’
If day is Tuesday then
Set meal t o ‘Shepherd’s pie’
…
If day is Friday t hen
Set meal t o ‘Fish and chips ’
Output meal
Sequential and nested selection
23
 In
OUBuild,
this
might
be
implemented using sequence of
selection instructions as in Figure 4.
Figure 4
 The Python equivalent of the is as
follows:
if day == ‘M’:
meal = ‘Meat loaf’
if day == ‘T’:
meal = ‘Shepherd\’s pie’
if day == ‘W’:
meal = ‘Omelette’
if day == ‘Th’:
meal = ‘Chilli’
if day == ‘F’:
meal = ‘Fish and chips’
print(meal, ‘today!’)
Sequential and nested selection
24
 The previous code is works perfectly but it is not very
elegant.
 Whatever day is input, the algorithm works its way
through every one of the five ‘if … then …’ instructions.
 A more elegant and more efficient algorithm can be
done using nested ‘if … then … else’ instructions.
 The nested structure prevents the algorithm
proceeding any further through the selection
instructions once it has reached the condition
corresponding to the given day.
Sequential and nested selection
25
 The nested structure looks as follows:
Input the day
If day is Monday then
Set meal t o ‘Meat loaf ’
else
If day is Tuesday t hen
Set meal to ‘Shepherd’s pie’
else
…
If day is Thursday then
Set meal to ‘Chilli’
else
Set meal t o ‘Fish and chips ’
Output meal
Switch instructions
26
 Some other languages (though not Python) have a
slightly neater way of dealing with such situations,
known as case instructions or switch
instructions, which allow for several different
courses of action to be taken according to the value of
a variable, and thus avoid the need for complex
combinations of selection instructions.
Switch instructions
27
For example, here is Java code that implements the selection instructions:
switch (day) {
case “M”:
System.out.println(“Meat loaf today!”);
break;
case “T”:
System.out.println(“Shepherd’s pie today!”);
break;
case “W”:
System.out.println(“Omelette today!”);
break;
case “Th”:
System.out.println(“Chilli today!”);
break;
case “F”:
System.out.println(“Fish and chips today!”);
break;
}
What is a good algorithm?
28
 One possibility is to measure ‘goodness’ in terms of which algorithms
are easiest to understand. If an algorithm is clear, it can be easier
translated into a computer program and tested for correctness.
 A second idea to think about is how much effort it will take to carry
out each algorithm. When we design an algorithm we expect to use
it many times, and so we want the algorithm to be efficient
and not require more effort and time the necessary.
 The first point is important: understandable algorithms result in
more readable computer programs that are easier to maintain.
 The second point is not quite as straightforward to answer. It may
not be immediately apparent that two algorithms performing the
same task can involve different amounts of effort.
 The following simple example shows how the choice of an algorithm
can make a lot of difference.
What is a good algorithm?
29
 Example :
 Suppose 100 guests attended a fete. How many
arithmetic operations would be required to
calculate the total cost of cupcakes by
Algorithm A Algorithm B?
 We can plot on a graph the number of arithmetic
operations required by Algorithm A and
Algorithm B with varying numbers of guests, as
shown in Figure 5.
What is a good algorithm?
30
Note the following:
 For both algorithms, the
number
of
operations
increases along with the
number of guests.
 Both
algorithms
produce
straight
lines
on
the
graph between the number of
operations and the number of
guests (i.e. linear relationship).
 Algorithm A is inefficient since
its line is steeper than that for
Algorithm B, showing that the
number of operations required
for Algorithm A grows more
rapidly as the number of
guests increases.
Figure 5
Swapping
31
 Swapping two items of any kind is a fundamental activity that we
perform in the real world, as well as being a key part of many algorithms,
including those used to sort data.
 Swapping is nothing more than exchanging positions.
 Let’s write a swapping algorithm. Specifically, you will write an
algorithm that will swap the values of two variables.
 To make the process simpler, we will present two variables using two
Post-it notes (small pieces of paper). We will label the first ‘item1’ and
the second ‘item2’ as shown in Figure 6.
Figure 6
Swapping
32
 Now, write ‘Bob’ on item1 and ‘Alice’ on item2, as shown in Figure 7.
Figure 7
 The two Post-it notes, item1 and item2, represent two variables. item1
has the value Bob, and item2’s value is Alice.
 We need to swap the values of item1 and item2. This can be done by the
following algorithm:
Set item2 to item1
Set item1 to item 2
Swapping
33
 Applying the algorithm results in item1 and item2 both have the value
Bob as shown in Figure 8! How can you solve this?
Figure 8
 To solve the problem, we need a temporary variable (Post-it note
‘temp’) as shown in Figure 9.
Figure 9
Swapping
34
The new algorithm follows 3 steps in sequence:
Copy the value in item2 to
temp, as shown in Figure 10.
Copy the value of item1 to
item2, as shown in Figure 11.
Copy the value of temp to
item1, as shown in Figure 12.
Figure 10
We can write down this sequence
of instructions as an algorithm:
Figure 11
1.
2.
3.
Set temp to item2
Set item2 t o item1
Set item1 to temp
Figure 12
Swapping
35
 This swap algorithm is a fundamental part of many more complex
algorithms and can be found at the heart of almost all major
systems such as: banking, stock markets and online shopping
sites.
 It’s only 3 lines long, but it is a key part of the modern world.
 This algorithm is straightforward to implement in OUBuild, as in
Figure 13.
 In Python, the code is as follows:
temp = item2
item2 = item1
item1 = temp
Figure 13
Sorting
36
 Sorting is an area where efficient algorithms are crucial
since it is one of the most common purposes for computers.
 You may have used sorting to reorganise your emails, or to
rearrange data in a spreadsheet.
 Google sorts their results by usefulness.
 Sorting is found in:
 Spell-checking in word processors.
 Compressing data so that it uses less disk space.
 Prioritising
tasks in the computers that control aircraft, industrial
plants and power stations to ensure safety.
 Arranging on-screen objects from the most distant to the closest to
ensure the graphics in 3D video games are drawn correctly.
What is sorting?
37
 Sorting algorithms take lists of unsorted data and turn them
into lists of sorted data.
 Sorting simply is the process of putting similar items into
order. For instance, we can sort:
 Numbers in ascending order (1, 2, 3 …) or descending order (…
3, 2, 1)
 Words alphabetically, in reverse alphabetical order, by length,
frequency of use, etc.
 Events ordered by dates.
 Items in an online shop by price, popularity, etc.
 and so on
Lists
38
 Here
is a short list of names sorted in alphabetical order :
Ahmad, Basil, Marwan, Saif, Ziyad
 A list is made up of items of data, each having a position in the list: the
first item is at position 1, the second at position 2, and so on …
 A list can also be described in terms of its length: this list has length 5.
Example:
 Here is a list of place names:
Salalah, Istanbul, Jerusalem, Cairo, Petra, Byblos, Dubai.
It appears to be unsorted
a. Is this list sorted?
7
b. What is the length of the list?
Byblos
c. What is the item at position 6?
d. What is the position of ‘Petra’ in the list? Position 5
Selection sort
39
 This algorithm repeatedly searches for the smallest or lowest
item in a list of unsorted data and moves the item to the end
of a list of sorted data.
 The algorithm repeats until all the data is sorted.
 Selection sort can be implemented using two separate lists:
one for unsorted data and another for sorted.
 Such algorithms are called not-in-place sorts. But they are
not often used in computer programs because there is a
more elegant way to sort using a single list containing both
sorted and unsorted portions.
 An algorithm that sorts items within the original list is
known as an in-place sort.
Selection sort
40
 The algorithm for the in-place selection sort can be written as
follows:
Selection sort
Repeat until (only l item of unsorted data remains )
Find t he lowest item in the unsorted data
Swap the lo west item with the first item in the unsorted data
 How does it work?
 Search through the list and find the smallest element.
 Swap the smallest element with the first element.
 Repeat
starting at second element and find the second smallest
element.
Selection sort
41
Example:
35
65
30
60
20
20 65
30
60
35
20 30
65
60
35
20 30
35
60
65
20 30
35
60
65
scan items 1 – 5, smallest 20
swap 35 and 20
scan items 2 – 5, smallest 30
swap 65 and 30
scan items 3 – 5, smallest 35
swap 65 and 35
scan items 4 – 5, smallest 60
swap 60 and 60
done
Bubble sort
42
 Like selection sort, the bubble sort algorithm is based on comparisons.
 Bubble sort works methodically through a list from beginning to end,
comparing each pair of adjacent items.
 If the two items are in the wrong order, then they are swapped.
 The algorithm then moves one position along the list and compares the
next pair, and so on.
 We can write the part of the algorithm that passes from the beginning to
end of the list, swapping adjacent items if they are not in order, like this:
Swapping pass
Starting at the beginning of the list
Repeat for (each pair of adjacent items )
If the items are in the wrong order then
Swap them
Bubble sort
43
 Here are three lists sorted using the swapping pass algorithm we have
developed so far. What characteristic do the last item in each of
the sorted lists share?
List before swapping pass
List after swapping pass
Marwan, Ziyad, Basil, Ahmad, Saif
Marwan, Basil, Ahmad, Saif, Ziyad
22, 4, 7, 100, 3
4, 7, 22, 3, 100
Salalah, Istanbul, Jerusalem, Cairo,
Petra, Byblos, Dubai.
Istanbul, Jerusalem, Cairo, Petra,
Byblos, Dubai, Salalah
 Answer: Our list is now partially sorted; after one swapping pass, the
last item is always in the correctly sorted position. However, the
remainder of the list needs further sorting.
Bubble sort algorithm
44
 More generally, a list containing n items will be sorted
after n − 1 swapping passes through it. So we can create an
algorithm to completely sort a list, by nesting the swapping
pass inside a loop as follows:
Bubble sort l
Repeat (length of list – l) times
Starting at the beginning of the list
Repeat for (each pair of adjacent items )
If the items are in the wrong order then
Swap them
Swapping Pass
Bubble sort algorithm
45
Example:
 Traverse a collection of elements
 Move from the front to the end
 “Bubble”
the largest value to the end using pair-wise
comparisons and swapping
1
2
3
4
5
6
77
42
35
12
101
5
Bubble sort algorithm
46
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
2
3
42 Swap4277
77
35
4
12
5
101
6
5
Bubble sort algorithm
47
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
42
2
3
4
7735 Swap3577
12
5
101
6
5
Bubble sort algorithm
48
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
42
2
35
3
77
7712 Swap 12
4
5
6
101
5
Bubble sort algorithm
49
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
42
2
35
3
12
4
77
5
101
No need to swap
6
5
Bubble sort algorithm
50
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
42
2
35
3
4
12
77
5
6
1015 Swap 101
5
Bubble sort algorithm
51
 Traverse a collection of elements
 Move from the front to the end.
 “Bubble” the largest value to the end using pair-wise
comparisons and swapping.
1
42
2
35
3
12
4
5
6
77
5
101
Largest value correctly placed
Bubble sort algorithm
52
 Notice that only the largest value is correctly placed
 All other values are still out of order.
 So we need to repeat this process
 If we have N elements and if each time we bubble an element, we
place it in its correct location.
 Then we repeat the “bubble up” process N – 1 times.
 This guarantees we’ll correctly place all N elements.
1
42
2
35
3
12
4
77
Largest value correctly placed
5
5
6
101
Bubble sort algorithm
N-1
53
“Bubbling” All the Elements
1
2
3
4
5
6
42
35
12
77
5
101
1
2
3
4
5
6
35
12
42
5
77
101
1
2
3
4
5
6
12
35
5
42
77
101
1
2
3
4
5
6
12
5
35
42
77
101
1
2
3
4
5
6
5
12
35
42
77
101
Merge sort
54
 Merge sort is a very popular way of sorting data, not only
because it is much faster than bubble sort for most purposes, but
also because it can be designed to work on parallel-processing
computers in which each processor performs part of the sort.
 Table1 shows generally how much longer it takes to sort a list
using bubble sort than using merge sort, assuming they are both
using the same unsorted data and implemented on the same
computer hardware.
 As you can see from the table, it is increasingly advantageous to
use merge sort as the number of items to be sorted increases.
 If you have a hundred items to sort, merge sort, on average, sorts
the items 50 times faster than bubble sort, whilst if you have a
million items it is nearly 167 000 times faster!
Merge sort
55
 Whilst most of us do not need to sort such volumes of data, sorting
millions, or even billions, of items is common place in large
organisations.
Table 1
Merge Sort Algorithm
How Does it Work?
56
It uses the Divide –and-Conquer paradigm.
 Merge-sort on an input sequence S with n
elements consists of three steps:
 Divide: partition S into two sequences S1 and S2 of about n/2 elements
each
 Recur: recursively sort S1 and S2
 Conquer: merge S1 and S2 into a unique sorted sequence
Base case :If a list has 1 element or 0 elements it is sorted.
Merge Sort Example 1
99
99
6
6
86 15 58 35 86
4
0
86 15
58 35 86
4
0
4
99
6
86 15
58 35
86
99
6
86
58
86
15
35
0
4
0
4
0
Merge Sort Example 1
99
Merge
6
86
15
58
35
86
0
4
4
0
Merge Sort Example 1
59
6
99
15 86
35 58
0
99
6
86
58
86
AOU – Lebanon M180
15
35
4
86
0
4
16 November 2022
Merge Sort Example 1
60
6
6
15 86 99
99
15 86
AOU – Lebanon M180
0
4
35 58
35 58 86
0
4
86
16 November 2022
Merge Sort Example 1
61
0
6
AOU – Lebanon M180
4
6
15 35 58 86 86 99
15 86 99
0
4
35 58 86
16 November 2022
Merge Sort Example 1
62
0
AOU – Lebanon M180
4
6
15 35 58 86 86 99
16 November 2022
Example 2
63
Use Merge Sort to sort the following array:
23
11
5
19
120
7
1
113
64
Merge Sort Example 3
65
Summary
66
Having completed this part, you should be able to:
 Describe what an algorithm is and provide everyday
examples.
 Describe the fundamental building blocks of
algorithms.
 Match parts of a small program in a language such as
Python or Java to parts of an algorithm.
 Use visual aids such as pieces of paper to follow an
algorithm.
 Learn different type of soring algorithms.
 Apply a sorting algorithm to a particular list.
Block 2 Part 5
Selection
MODULAR
PROGRAMMING
AOU UNIVERSITY
Dr Radwan-Associate Lecturer
Introduction
2
 So far in the course, you have gained
experience
with
the
three
main
programming
structures:
sequence,
selection and repetition. In this meeting you
will:
 Learn about nesting programming structures.
 Learn problem-solving with custom blocks .
 Practise using your problem-solving skills and applying
the programming ideas.
Nested structures
3
 Activity 5.1 contains the Octopus Hunt program (Figure 1).
 Start the program with the green flag and follow the instructions to
play the game.
 The octopus will simply follow your mouse pointer to get away from
the shark. Stop the program with the red stop icon
Figure 1
Nested structures
4
Look at the code of
Activity 5.1 (Figure 2)
which
has
loops
within loops (i.e.
Nested loops).
A. Can you identify
the inner loop?
What does it do?
B. Can you identify
the outer loop?
What does it do?
Figure 2
Nested structures
5
Solution:
A. The inner loop is the one formed by the repeat_until{} block.
It makes the shark chase the octopus – that is, repeatedly move
towards the octopus, appearing animated, until the octopus is
caught.
B.
The outer loop is the one formed by the forever{} block. It makes
the shark chase the octopus repeatedly, each chase ending with the
shark appearing to eat the octopus and displaying the duration of
the chase.
Reducing complexity
6
 Some complexity in programming is expected.
 If you want a program to do an interesting and complex task, it is
expected that it will not be short and straightforward.
 It is also possible you will not get the program right straight away.
 However, there are some techniques that can help you manage
complexity by structuring your programs into parts, so they are
simpler to create, and to understand afterwards.
 The basis for this is the Make a Block facility for creating custom
blocks.
 Creating a block to implement a task needed in several scripts, so
that the single block can be used in those scripts, rather than
duplicating code.
 Open Activity 2.12 (Figure 3)
1. create custom
block : ”wake_up”
7
Call ”wake_up” block
2. create custom block:
”go_to_sleep”
Call ”go_to_sleep” block
Call ”wake_up” block
Call ”go_to_sleep” block
Figure 3
Reducing complexity
8
 Instead of having to duplicate the code for ‘waking up’ and
‘going to sleep’ in each when[]key_pressed script, the
code for each was created just once.
 Then whenever needed, the block is called, with its name,
resulting in its code to run.
 Using custom blocks to implement duplicated tasks has
many advantages:
Save time, effort and space.
 Reduce the risk of error.
 Make the structure of the code simpler and hence easier to
understand (i.e. make your code more readable).

Nested Loop
9
 We now consider how and why loops may be nested inside each other.
 Activity 5.2 have provided use the blocks stamp and clear from the Pen
palette, shown in Figure 4.
The stamp block stamps a copy of a sprite’s costume onto the stage.
 The clear block clears all such images from the stage.

 Figure 5 shows a loop that makes Owl stamp a row of eight owl images,
each colored slightly differently.
 It does this by repeatedly (8
times) stamping a copy of
Owl’s costume on the stage;
moving Owl 40 steps to the
right; and changing its
color.
Figure 4
Figure 5
Nested Loop
10
 Suppose that we want to produce two rows of owls, as in Figure 6.
Figure 6
 One way to do this would be
to use the row-producing
loop (Figure 5) so that the
Owl makes the first row.
Then, move the Owl down
and left and then make a
second row by repeating the
same row-producing loop
(Figure 7).
Figure 7
Nested Loop
11
 What is we want to produce six rows of owls, as in Figure 8.
 You could add 6 row-producing loops, with Owl moving down and left
between each, but this would produce a very long script.
 You can wrote a much simpler
code if you recognize that there
is a repeated task involved here,
that is:


making a row.
moving down and left.
 Like any repeated task, it can be
achieved using a loop.
 The script can be amended so
that Owl repeatedly (6 times)
makes a row and moves, as
shown in Figure 9.
Figure 8
Nested Loop
12
Figure 9
Modular programming
13
 Modular programming (or component-based programming) is
concerned with creating programs organized as relatively
small modules (chunks of code / components) which together
achieve the overall tasks required of the program.
 Modular programming enables the programmer to focus on a
program at varying levels of detail, in a structured manner.
 This tends to result in code that is:
 Easier to create, with fewer errors, because the programmer can
concentrate on implementing one small task at a time, in a
separate component.
 Easier to understand, because the structure of the code is clearer.
Reuse & Refactoring
14
Reuse
 Professional developers are concerned with the potential for
future reuse of their components, as well as how components
may simplify their current program.
 They want their components to be easily reused in future;
forming clear specifications is one aspect of this.
Refactoring
 Refactoring a program concerns amending its structure to
improve it whilst not changing what it does.
 To the user, the program behaves identically, but ‘inside the box’
the program code is (if refactoring is done well) better organized,
more modular and easier to understand, and in some cases
potentially reusable.
Problem-solving in action
15
 As problems get more complex, we need
techniques which enable us to break down
solving the problem into smaller parts that
can be more easily managed.
 Sub-processes may be identified which
represent important distinct tasks.
 Each sub-process can be implemented as a
component.
 By doing this we simplify our program.
Problem-solving in action
16
1. Designing components
 Sub-processes,
which will be implemented as
components, can be identified early in designing the
algorithm.
 Sometimes, this ca be identified later.
 Some people prefer to give more detail to a complex
algorithm before thinking in terms of partitioning into
sub-processes; some like to break down the structure.
 Both personal preference and the form of the
specification influence the design process; what matters
is that you end up with an algorithm that is partitioned
sensibly into understandable parts.
Problem-solving in action
17
2. Implementing components
 Partitioning the processing involved in an algorithm into smaller, more
manageable sub-processes makes the algorithm design process simpler.
 When what is involved is more complex, retaining those sub-processes
as distinct parts of the final algorithm can make the algorithm itself
easier to understand and then to implement.
3. A bottom-up approach
 Individual components need to be implemented first, checked and
tested, and finally the whole program will be put together.
 In general, it is sensible to implement first any component(s) that do
not depend on the results of any other components; then to implement
those that only depend on the results of components already
implemented; and so on until all components and scripts are created.
 This is called a bottom-up approach
Problem-solving in action
18
4. Testing and debugging a complete program
 The bottom-up approach applies also to testing complete programs
which contain newly created components.
 If we simply test the overall program and a test fails, it can be hard
to locate the source of the problem. Is it in the components, or in the
way they have been used?
 Instead, we can start by testing each component in turn, again
beginning with those that do not depend on other components.
 We make sure that each of them works correctly; if not, then we
correct the problem.
 Making sure a component meets its specification is also important
for reuse.
 Once we have tested and, if necessary, debugged our components,
then we can progress to testing the overall program.
Problem-solving in action
19
When testing a complete program that involves
already-tested components, if a test fails there
are some common errors worth looking for:
 The wrong components may have been used, or the
right ones may have been used but in the wrong order.
 Data upon which a component depends may have been
set incorrectly, or incorrect data supplied to the
component.
 A component’s results may have been used incorrectly.
Problem-solving in action
20
Example (Program specification)
 My grandson wanted to know the names of the birds that he saw in my garden
during one morning. I told him to think about the birds and describe what he saw.
He said that the first birds he saw were different colours: two of them were brown
but different sizes, and one was blue and yellow.
Analysis and description:
 I explained that the larger of the two brown birds was a song thrush and the smaller
brown bird was a sparrow. The blue and yellow bird, which was about the same size
as the sparrow, was a blue tit.
 Later on, another bird appeared that was about the same size as the sparrow, but
although it was mostly brown, it had a red chest. I told him that this was a robin.
Another bird was the same size as the song thrush but black all over. This was a
blackbird.
 Finally, two much larger birds came into the garden and scared the smaller birds
away.
 One of these was mainly black but had some white on it as well.
 This was a magpie. The other was grey, blue and pink and was a wood pigeon.
Problem-solving in action
21
 I found a bird field guide with pictures of the birds (Figure 10).
 However, my grandson didn’t think he would be able to remember
them when I wasn’t there to show him the guide.
 To help my grandson I want a program that will ask him for key
facts about a bird and suggest which bird he might have seen.
 I will assume for simplicity that these are the only birds that come
in to my garden.
Figure 10
Problem-solving in action
22
Design an algorithm
 There are two types of fact: size and colour.
 With the birds described here, knowing whether the bird is
small, medium or large and knowing the colour or colours
enables me to identify the bird.
 I can write down an initial draft:
1.
Input key facts about the appearance of the bird
Decide name of bird
Output name of bird
Problem-solving in action
23
 The situation is complex to write down in words, but in these
situations a diagram helps.
 A selection to decide the bird name can be made in two
stages in terms of two questions:
1.
2.
The answer to the first question (‘What is the size?’) narrows
down the possibilities;
Then the answer to the second question (‘What is the colour?’)
enables the bird name to be determined.
 I draw the diagram in Figure 11 to show the two stages, the
questions, the possible answers, and finally the output.
 This is a diagrammatic representation of the multiple-stage
selection involved in my algorithm (sometimes called
a decision tree).
Problem-solving in action
24
Figure 11
Problem-solving in action
25
 I can now start to add some detail to my algorithm.
Input size
Input color
Use size and color to decide name of bird
Output name of bird
 Following my decision tree, I refine my algorithm as follows:
Input size (small, medium or large)
If small then
Input color (brown and red, brown or blue and yellow)
Decide name of bird
If medium then
Input color (brown or black)
Decide name of bird
If large then
Input color (black and white or grey, blue and pink)
Decide name of bird
Output name of bird
Problem-solving in action
26
 My algorithm is starting to look quite complicated. So I review it, and identify
some sub-processes: deciding on a bird name, given the bird color.
 There are, in fact, three different sub-processes, since the details of each
depends on the bird size, though I expect that each will follow a common
pattern.
 If I separate them out, my algorithm starts to look a little more manageable, as
shown below.
Problem-solving in action
27
Decide on components
 My algorithm sets out some sub-processes.
 Each represents a reasonably substantial and distinct task, so to
simplify my program I will implement each as three separate
component.
 It won’t matter which order I implement them in as there are no
dependencies.
1
Problem-solving in action
28
2
3
Problem-solving in action
29
Implement
 The program is shown in Figure 12. It uses three custom blocks:
identify_small_bird, identify_medium_bird, identify_large_bird.
2.
Figure 12
Summary
30
Having completed this part, you should be able to:
 Describe the tasks performed by an OUBuild program involving
nested selection and/or repetition and/or custom blocks
 Amend or create a small OUBuild program involving nested
selection and/or repetition to meet a specification, making
appropriate use of custom blocks
 Create an algorithm involving nested selection and/or repetition to
solve a problem, including identifying sub-processes
 Implement a small OUBuild program involving nested selection
and/or repetition to solve a problem, including defining custom
blocks to implement sub-processes that represent substantial,
cohesive tasks.
Block 2 Part 3
LOOPS
AOU UNIVERSITY
Dr Radwan-Associate Lecturer
Introduction
2
 Humans may get tired of repeating the same thing over and over,
but computers are ideally suited to repetitive tasks.
 All programming languages include structures for causing
instructions to be executed repeatedly.
 Repeated execution is often referred to as repetition or looping.
 There are three general types of loop:
1.
2.
3.
Loops whose contents execute a fixed number of
times
Loops whose contents execute indefinitely
(potentially forever)
Loops whose contents execute repeatedly
dependent on some Boolean condition.
 OUBuild looping blocks are in the Control palette
(Figure 1).
Figure 1
Introduction
3
 Do Activity 4.1 (Figure 2) which introduces you to a program involving
conditional loops using the block repeat_until< > { }
 This block runs repeatedly until the condition that is in the
repeat_until{} block’s input box reports true.
Figure 2
Forever loops
4
 The forever{ } block, refer to as a forever loop (See activity 4.2).
 Forever loops: loops whose contents run over and over,
indefinitely.
 They are sometimes referred to as infinite loops though in fact they
can be stopped.
 Many programs you interact with every day use such loops, such
as web servers, your computer’s operating system, and so on.
 Forever loops in OUBuild are typically used to implement tasks
that should continue indefinitely throughout a program.
 Examples: implementing continuous background sound, or
continuous sprite movement.
 OUBuild implements loops that execute forever with
the forever{} block, shown in Figure 3.
Figure 3
Forever loops
5
 forever{} is a foot block: nothing can be
attached underneath it.
 A flow chart illustrating the forever{} block is
very simple, as shown in Figure 4.
 Forever loop can be stopped in various ways,
including when a stop[ ] block is run.
 A stop[ ] block enables a forever loop to be
stopped intentionally.
 A stop[ ] block takes one of three possible
input values, as follows:
1.
2.
3.
Figure4
all: stops all scripts in the program
this_script:
stops just the script that contains this block
other_scripts_in_sprite:
stops all other scripts in the sprite
concerned, except the one that contains the stop[ ] block.
Conditional loops
6
 In Meeting 3 you met Boolean blocks and their use as
Boolean conditions for if< >then{ } and if< >then{ }else{ }
blocks.
 Just as OUBuild can use a Boolean condition to determine
whether or not to execute a particular set of instructions, it
can also use a Boolean condition to determine whether or
not to execute a loop’s contents.
 Loops that work like this are called conditional loops.
 OUBuild implements conditional loops with
the repeat_until{} block from the Control
palette (Figure 5).
 A flow chart illustrating the repeat_until{}
Figure 5
block is shown in Figure 5.
Conditional loops
7
 When




OUBuild
encounters
a
repeat_until{ } block, it first checks the
value of the Boolean condition.
If it is true, then the loop contents are not
run at all and OUBuild moves on to any
blocks after the repeat_until< >{ } block.
If it is false, the loop contents are run,
from the first block to the last, and then
OUBuild again checks the value of the
condition.
If it is now true, then the loop contents
Figure 6
are not run again and OUBuild moves on
to
run
any
blocks
after
the
repeat_until{} block; If it is false, then
the loop contents are run again, and so on.
Before each potential run of the loop contents, OUBuild checks the condition to
determine whether or not to run the loop contents.
Forever loops
8
 Exercise: Write a loop to print the numbers from 1 to 10.
 The code can be implemented in OUBuild as shown in Figure 7 and Figure 8
which are equivalent.
Figure 7
Figure 8
 The change[ ]by[ ] block provides a simple way of increasing or decreasing a
variable’s value.
 To increment a variable i by 1 we use:
 To decrement a variable i by 1 we use:
Conditional loops
9
 Depending on the precise requirements, it can therefore
be necessary to consider carefully:
1. whether and how to ensure that loop contents are run
at least once – that is, that the loop’s condition
reports ‘false’ initially
2. whether and how to ensure that loop contents are not
run indefinitely – that is, that the loop’s condition
reports ‘true’ at some point.
Fixed loops
10
 The repeat[ ]{ } block, which refer to as
fixed loops, runs the blocks inside the
loop’s contents a specific number of
times, given by the value in its input
box, which should be a non-negative
integer.
 Once the contents have been executed
the specified number of times, the
execution moves on to the next block,
as illustrated in the flow chart (Figure 9).
 The repeat[10] block (Figure 10)
repeats the loop ten times.
 We will use the term iteration to refer to
a single run of the loop contents
Figure 9
Figure 10
String processing
11
 Text processing refers to the manipulation of text (words) by
a computer.
 Text may need to be manipulated in many different ways. Think
of a word processor, for example, which, given a piece of text,
might:
search for the first occurrence of a specific word or character.
 replace every occurrence of a specific word or character with
another.
 insert a character according to a particular rule, for example, a
space after each full stop.
 search for all invalid ‘words’, that is, words that don’t appear in a
dictionary.
and so on.

Do Activity 4.8
String processing
12
Activity 4.8 illustrates a code (Figure 11) that applies a decorative
effect to any word entered by the user, with stars (asterisks) added at
the beginning and end and between each pair of characters.
 For example, if you enter the word “rover”, it prints *r*o*v*e*r*. (See
Figure 12)

Figure 11
String processing
13
Figure 12
String processing
14
 A variable such as position is known as an index variable, because it is
used to index or provide access to an individual item of data within a
collection.
 Here, the characters within a string are accessed in turn using their
successive positions within the string.
 We say that an index variable enables a program to iterate over a
string (i.e. to repeatedly step through the string’s characters,
processing them one by one).
 With length_of[word] as the loop’s input value, the number of iterations
is the same as the number of characters in the user’s word.
 The basic idea of using an index variable to iterate over a string’s characters
one by one is quite easily adaptable.
 For example, to enables iteration to start at a character further on in the
string or finish at a character before the final one.
 Whenever it is required to process characters in a string, a loop in
conjunction with an index variable is often the way to proceed.
List processing
15
Strings and lists have much in common:
 A string is a sequence of characters, each at a numbered
position.
 A list is a sequence of data items (numbers or strings),
again each at a numbered position.
 You have seen that OUBuild provides some similar blocks
for each, for example:
▪
▪
there is a block that reports the length of a string, and there is a
block that reports the length of a list
there is a block that reports the character at a specific position in a
string, and there is a block that reports the item at a specific
position in a list.
List processing
16
 Suppose that you want to create a List called sentence and
initialize it by a number words entered by the user.
 You will definitely use the add[ ]to[ ] block but you don’t know
how many words the user will want to enter!
 This can be done with a repeat_until< >{ } block in
conjunction with what is known as a sentinel value.
 Sentinel value is simply a value used to indicate that the loop
should end.
 The user enters this value to indicate that they have no more
words to enter; then the loop stops.
 Example: repeat_until { … }
Q is the sentinel value.
 Check Figure 13 and Figure 14.
List processing
17
1. Read before
the loop
2. Check for
sentinel value
3. Read again at
the end of the loop
Figure 13
List processing
18
Figure 14 visualizes how the
code works with input:
‘tea’ , ‘for’, ‘two’, ‘q’.
Figure 14
List processing
19
 A list allows a collection of data to be stored together and
processed together.
 Loops can be important tools in enabling user input to be stored
in lists and also in processing data held in lists.
 Of course, just as with strings, considerable variation is possible.
 For example, a list may be iterated over in reverse order by using
an index variable whose value decreases.
 Once a list holds a collection of numbers, the numbers can be
processed, and looping techniques are often useful. It might be
required, for example, to:
find the largest number in the list, or the smallest
➢ find the mean (average) of the numbers
➢ list the numbers in order, from smallest to largest.
➢
Numerical processing with lists
20
How can the smallest (lowest, or minimum) number in a list be found in the list
of numbers?
The algorithm is as follows:
➢ Set a variable, smallest_number, say, to the first number in the list, as is done
in the incomplete script.
➢ Compare the second number in the list with the value of smallest_number; if
the second number is less than the value of smallest_number, set
smallest_number to the second number.
➢ Compare the third number in the list with the value of smallest_number; if the
third number is less than the value of smallest_number, set smallest_number
to the third number.
➢ Continue in this manner to the end of the list.
➢ Example on finding the minimum temperature in a list of temperatures is given
in Figure 15.
Note that the iterations should start at the second number in the list,
until the final number in the list. This means that in a list of n
elements, there must be n – 1 iterations.
Numerical processing with lists
21
Figure 15
Numerical processing with lists
22
How can the sum (total) of the elements of a list be found in
the list of numbers?
The algorithm is as follows:
➢ Set a variable, sum, say, to 0.
➢ Iterate on the list elements one by using an index.
➢ Add the value of each element one by one to sum.
➢ If you want to find the average, you need to use the
formula: average = sum/(length of list). This
should be done outside the loop.
➢ Example on finding the average to temperatures is given
in Figure 16.
Numerical processing with lists
23
Figure 16
Problem-solving with loops
24
 What clues are there in a program specification that tell us that
a program may need to repeat something?
 Words such as ‘for each’, ‘how many’, ‘every’, ‘until’, ‘total’,
‘while’, etc.
 These word may appear on their own or in combination, such as
in the following sentences:
 For each child whose name is in the list, get the age and address of
the child from the user.
 Check the password to see how many times the space character is
included.
 Add the numbers together until the total exceeds 100.
 Play the music while the game is on.
 These sentences can be reworded to use terms such as ‘Repeat
(…) times…’or ‘Repeat until (…) …’, or ‘Repeat forever…’ which
are similar to the OUBuild programming structures for
repetition.
Problem-solving with loops
25
Common repetition errors
If a test fails, then, in trying to trace and fix a bug, it is useful to bear in mind
common errors that tend to be made in programs of the sort we are testing.
Three kinds of error specific to repetition are:
 a loop condition is incorrect
 data involved in a loop condition is not changed correctly within the loop’s
iterations
 an index variable is not changed correctly within the loop’s iterations or is not
initialized correctly.
 These sorts of error can lead to various problems, such as:
➢
➢
➢
➢
a loop not executing at all when it should,
executing indefinitely when it shouldn’t,
accessing the wrong item, or
attempting to access a non-existent item in a list or string.
 Small slips in creating a loop condition or in manipulating an index variable
often lead to either the first or last item being processed incorrectly whilst the
other items are processed correctly.
Block 2 Part-2
NUMBERS, STRINGS AND
LISTS
AOU UNIVERSITY
OUBuild
2
 For An Introduction to OUBuild Go to:

Introduction
3
 In this meeting, you will learn how to create
increasingly powerful, interesting and varied
programs.
 The main topics you will be introduced to are:
 Working with numbers, strings, lists and variables in
OUBuild.
 Learn how to problem-solve in the context of
programming. i.e how to take an idea for a program
and develop it until you have a working program.
Introduction
4
Programming with numbers
 Working with numbers is a common programming task.
 Examples: ticket prices, ID numbers, PIN, …
Programming with strings
 Strings are sequences of characters such as ‘Welcome to
TM111!’.
 Examples: names, Passwords, …
Programming with lists
 Lists provide a form of data storage that can hold many
items of data at the same time.
 Lists enable programs to work with collections of data.
 See activity 2.1
Prototype programs
5
 A prototype is a small, simplified version of what might
eventually be part of a much larger program.
 Rather than attempting to create a full working system all
at once, it is common for parts of it to be developed
individually.
 Each of those parts may be developed in increasingly
complex versions, starting with quite simple prototypes of
what will eventually be required.
 This enables the programmers to find out potential
problems early on as well as enabling all those involved,
including the potential users, to get a better idea of what
the program will look like.
Variables
6
 Programs often need to keep track of data while they are
executing. For example:
 To keep track of user’s input.
 To keep count of something.
 OUBuild provide a mechanism known as a variable for
doing this.
 You can think of a variable as being a sort of named box in
OUBuild’s memory into which a program can put an item
of data, and then retrieve it again later.
 The reason why it is called a variable is that the value it
stores may vary over time.
Variables
7
 The programmer chooses the name of a
variable.
 It is good practice to choose meaningful
names for your variables,
 This helps you to remember the
purpose of variables in your programs
and also help other people to read and
understand your programs.
 In OUBuild, variables are created using
the Data palette, by clicking on the
‘Make a Variable’ button (Figure 1).
Figure 1
Numbers
8
Introduction to numbers in OUBuild
 Numerical calculations are at the heart of many powerful and
varied programs, from games to ticket price websites to
space rocket guidance systems.
Example Currency exchange
 Exchanging currency from Kuwaiti KD to Dollars ($)
involves the exchange rate.
 If the exchange rate is 3.15 and a customer wants to
exchange 300 KD, then the equivalent amount in Dollars is
300 * 3.15 plus charge of a commission if not free.
 See Activity 2.2
Precedence and Nesting
9
 When nesting number blocks, it is important to ensure that
calculations are carried out in the right order, matching the required
arithmetic calculation.
 For example, when performing the calculation 2 + 7 / 5, you should
first divide 7 by 5 (giving 1.4) and then add that number to 2, giving
3.4 as the result.
 Nesting of number blocks relates to precedence – that is, to the
order in which operations within a calculation are carried out.
 In the absence of brackets, multiplication and division have
precedence over addition and subtraction, meaning that they are
carried out first. Therefore, 2 + 7 / 5 is different than (2 + 7) / 5
 The order of precedence is BIDMAS : Brackets, Indices (powers),
Division, Multiplication, Addition, Subtraction.
 See Activity 2.3
Rounding, constants and comments
10
See video: https://www.youtube.com/watch?v=mts_8NoxvNo

 Explore activity 2.4 in your text
 The rules of rounding are:
If the next digit along from the decimal place we are rounding to is
less than 5, then we round down.
2. If the next digit along is 5 or more, we round up.
 Examples:
 Round 129.834 to one decimal place → 129.8 (rounding down)
 Round 3.7681 to two decimal places → 3.77 (rounding up)
 Round 133.501 to the nearest whole number → 134 (rounding up)
1.
 In OUBuild the key block is: round[ ],
Rounding, constants and comments
11
 Constants stored in a variable, but the value of the
variable will not change as the program runs.
 Constants typically named using capitals and may hold
any kind of unchanging data.
 A constant represents fixed data that is known to the
programmer whilst creating the program, and hence
that can be built in to the program.
 Code that is largely self-explanatory, for example, using
variables with meaningful names, is sometimes referred
to as self-documenting.
Rounding, constants and comments
12
 Comments provide the human reader of code with
explanation. They can help readability and for program
maintenance. You can add text comment to your program
any where. Text comments within programs, designed
only for the human reader. OUBuild ignores them when
running the program. Used to provide explanation.
 Maintenance is about keeping programs useful and
correct as they are used over sometimes long periods of
time.
 See activity 2.5
Strings
13
 A string can be visualized as a sequence of numbered slots, each
holding a character.
W
e
l
c
o
m
e
1
2
3
4
5
6
7
8
t
o
9
10 11 12 13 14 15 16
T
M
1
1
1
 The join[ ][ ] block joins two strings, appending the string in its second
input box to that in its first to form a new string
 Example: if the variable name has value ‘Mohammad’, then
Join [‘Hello’] [name] reports “Hello Mohammad”
Join [12] [34] reports 1234
But
[12] + [34] reports 46 (perform calculations)
 See Activity 2.6 ( password generator)
Strings
14
 The letter[ ]of[ ] block reports the character at a particular position
in a string.
 The length_of[ ] block reports the length of a string – that is, the number
of characters in it. Length of [“Welcome to TM111”] reports 16
Examples:
Suppose msg = “Welcome to TM111” then:
Letter[1] of [msg] reports ‘W’
Letter [ length_of [msg] ] of [msg]
reports
‘1’
Join[letter [length_of [msg]- 6] of [msg]] [join[letter[15] of [msg]] [letter [1] of [msg]]]
reports ’ o1W’
 Incremental construction can enable multiple strings to be joined without
complex nesting or use of extra variables.
 A general technique that can be used more generally whenever a value
can be constructed in stages.
 See Activities 2.7 and 2.9
Examples
15
Figure2: Program to print welcome messages for the user
Examples
16
Figure 3: Program to convert from Kuwaiti Dinars to Dollars
Lists and custom blocks
17
 Data in the form of a number or a string can be
stored in a variable.
 At any given time, a single variable can store
just one item of data.
 A list can store many items of data at a time.


a list may hold any kind of data (numbers and
strings).
items can be added to and removed from a list as a
program is running
Figure 4
 A list can be visualized as a sequence of slots,
each holding an item of data.
 Slots are numbered, starting from 1.
 To create a list, select the Data palette and click
on the ‘Make a List’ button (Figure 4).
 Lists are empty when first created (Figure 5).
Figure 5
Lists and custom blocks
18
 Some of the key blocks for programming with lists are shown in Figure 6.
 See Activity 2.10
Figure 6
Lists and custom blocks
19
 The add[ ]to[ ] block creates a new slot at the end of a list and
stores item in it (Figure 7).
Figure 7
 add[ ]to[ ] block with nothing entered into the first input box adds an
empty string to the end of the list (Figure 8).
Figure 8
Lists and custom blocks
20
 The same item can be included more than once in a list,
stored in different positions (Figure 9).
Figure 9
 The length_of[ ] block reports the length of the list (i.e. the
number of items).
Lists and custom blocks
21
 The item[ ]of[ ] block reports the item at a specified position in a list.
 Enables a program to access an item in a list, given the item’s position.
 The delete[ ]of[ ] block removes an item at a specified position in a
list.

Subsequent items are moved down one position to fill the gap and the list
length is decreased by 1.
 The insert[ ]at[ ]of[ ] block inserts an item at a specified position in a
list.

Subsequent items are moved up one position and the list length is increased
by 1.
 The replace_item[ ]of[ ]with[ ] block replaces an existing item at a
specified position in a list.

The original item is overwritten and the list length is unchanged.
 Can you tell what is the delete[all]of[ ] block ?
Lists and custom blocks
22
Exercise. Given a list: Courses as shown in
Figure 10. Report the following :
1. item[3]of[Courses]
2. insert[TM112]at[4]of[Courses]
3. replace_item[8]of[Courses]with[M105]
After running all blocks in the sequence at
once, what will the list Course looks like?
Draw it.
Courses
1
2
3
4
5
6
7
8

M 129
EL 111
TM 111
M 131
M 132
M269
length: 8
Figure 10
Strings and lists
23
Similarities between Strings and lists:
 A string consists of a sequence of characters; a list consists of a
sequence of items.
 Each character or item can be accessed using its position.
 Both have Length.
Differences between Strings and lists:
 You can insert an item into a specific position within a list, but
there is no block that inserts a character into a string.
 Do Activity 2.11 (self-assessment)
 Do Activity 2.12 (complete it by yourself)
 Do Activity 2.13 (self-assessment): Adding visual and audio
features followed by activity 2.14.
From ideas to programs
24
 Program
specifications typically arise from
problems which might be expressed in English such
as ‘How do I calculate the price of some theatre
tickets?’ or a game or a calculation or any similar
enquiries.
 Problem-solving in the context of programming
involves working from a specification to the:
 implementation: of a program that does the task required (i.e.
a solution to the problem);
 testing: checking whether a program really does solve the
problem as required or has errors (bugs); and
 debugging: identifying and fixing any bugs.
From ideas to programs
25
Algorithms and problem-solving
 An algorithm can be considered as a step-by-step
instructions to complete a particular task to solve a problem.
 To create a program, we need to be able to set out a step-bystep solution: an algorithm.
 However the raw material we start with, the specification, is
often quite unstructured.
 Identifying the steps needed in an algorithm and writing
them down clearly is a key skill that needs to be developed,
and it requires lots of practice.
 Taking the problem-solving process in two stages: design
and implementation makes things easier.
Problem-solving in action
26
Designing an algorithm, implementing a program
 Do Activity 2.15 in your text.
 Creating an algorithm in simple natural English.
For example:
Multiply number of full price tickets by full ticket price.
Or:
Set total for full price to number of full price tickets multiplied
by full ticket price.
 Look at the program specification and then design your algorithm,
make a set of tests intended to uncover any ways in which the program
does not meet the specification.
 In testing, valid data are involved including ‘extreme’ situations such as
an input of 0.
Problem-solving in action
27
Acceptance testing is a key stage in commercial software development. A client
will not accept new software unless they are convinced that it does the job
required. Convincing them involves carrying out sometimes thousands of tests to
check every conceivable aspect of the specification, including every possible
combination of different kinds of input.
 We can set this out in a
small table showing the
inputs with the expected
results (Table1).
 The next step is to run the
script
with
each
combination of inputs .
 Then start debugging.
Table 1
Problem-solving in action
28
In trying to trace and fix a bug, it is useful to bear in mind
common errors that tend to be made in the sort of programs we
are testing such as:
 incorrect data stored
 data stored in the wrong variable
 incorrect variables used in calculations
 wrong number block used (for example, []+[] instead of []*[])
 steps implemented in the wrong order
 initialisation incorrect or missing
 incorrect nesting of calculations
Do Activity 2.16.
Problem-solving in action
29
Problem-solving: worked example
 In a particular supermarket, the normal price of a 1.5-litre
bottle of cola is £2. However, sometimes there is also a
special offer on for the same brand of cola. A program is
required to ask the user the conditions of the special offer
(the price of the special offer; how many bottles the offer
involves; and the volume of each bottle in the offer) and then
to tell the user the difference in price per litre (to the nearest
penny) between the special offer and the normal offer so that
the user can decide which to buy.
Problem-solving in action
Design an algorithm (Figure 11):

What data is needed?
Supplied data: the price of the special offer, the number of bottles in the special offer, the volume of each
bottle in the special offer – all inputs
Fixed data: the normal price, the normal volume



Next, what more precisely is required?
Calculate the difference (special offer price per litre – normal …