CP4 Computing June 20003

1(a)

There are various types of human computer interface (HCI).

(i)

For each of the following types of HCI, describe a situation which could sensibly use this type of HCI and give one reason why this would be beneficial. You should use a different situation in parts I and II.

I. Keyboard input.

[2]

a PC being used for word processing
characters can be easily typed into a document.

II. Handwriting input.

[2]

adding a signature to forms on a hand-held computer.
the signatures cannot be forged.

(ii)

There are particular problems associated with handwriting input. Describe two such problems.

[2]

each person's writing is different and the computer may have difficulty recognising the characters.
different languages use different character sets (Chinese, Arabic etc)

(b)

Give two reasons why design validation is necessary when a computer system is being developed.

[2]

to make sure the design will achieve the objectives of the new system.
if the design is inappropriate it will be very difficult to alter it at a later stage.

2(a)(i)

Using 8 bits and two's complementation where appropriate, convert each of the following numbers to binary:

[1]

00011010

II.

-20

[1]

11101100

(ii)

Use binary addition and show your working to demonstrate that
26 - 20 = 6

[2]

(26)   00011010
(-20) 11101100 +
         ---------
     (1)00000110 which is 6

(b)

Show the effect of an arithmetic shift right by one place on the following 8-bit number:

10101011

[1]

11010101

The following binary tree has been produced by inserting the names Jones, Fergusson, Musabe, Ahmed, Venables, and Koen in that order.

In each case, the left pointer indicates the condition:
earlier in the alphabet

(i)

Copy the diagram then add the names Cooper, Yeats and Ho in that order.
(You may use just the initial letters of all names if you wish.)

[3]

(ii)

Comment on the overall shape of the original tree and state what effect this has on the speed of access to an existing element in the tree.

[2]

the shape is symmetrical about the root node..
..which would speed up access to a node.

(iii)

I. Draw a new tree for the case where the same names are inserted in the order:
Ahmed, Cooper, Fergusson, Ho, Jones, Koen, Musabe, Venables, Yeats.

[1]

II. Comment on the shape of the new tree.

[1]

NOT symmetrical about the root node...it is all one long branch...

III. Comment on the speed of access in the case of the new tree.

[1]

This will make the speed of access much slower.

A queue is a type of data structure.

(i)

Explain what is meant by the term data structure.

[1]

a way of organising data.

Why are data structures used in computing?

[1]

because it makes access to the data faster and easier to program.

(ii)

Explain, using a diagram, the term queue, and explain what should happen when an attempt is made to remove an item from an empty queue.

[3]

A queue is a FIFO (First In First Out) data structure,
..with two pointers indicating the start of the queue (Start) and the end of the queue (End)
If an attempt is made to remove an item from an empty queue, an error message should be output.
This queue has 3 items. A new item would be added at Num 5, and the next item to be removed would be Lynda.

Num	Item
5
4	Thomas	End = 4
3	John
2	Lynda	Start = 2
1

(iii)

When would a queue be used in a computer system?

[1]

Output sent to a printer would be added to a queue.

Why is a queue the most appropriate data structure in this case?

[1]

because the first item added to the queue should be the first item printed.(FIFO)

5(a)

Write down the truth table for the EXCLUSIVE OR (XOR) operation.

[2]

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

(b)(i)

Carry out a bit-wise XOR operation on the following:

Data = 10001101

Key = 11011010

[2]

01010111

(ii)

State what the results would be if you carried out a bit-wise XOR on your answer to part b(i) and the number Key.

[1]

The answer would be 10001101 - ie Data

(iii)

State a security use which this operation might be used for.

[1]

data could be encrypted using this operation and decrypted by XORing with the key to get the original data.

6(a)

Backus Naur Form (BNF) is often used in defining the grammar (syntax) of a programming language. Why is BNF preferable to English for this purpose?

[1]

BNF gives a logical structure to the syntax definitions..
it is closer to the way the compiler checks the syntax of a program.

(b)

One way of defining a positive decimal number is :

one or more digits, followed by a decimal point, followed by one or more digits.

For instance, the following are covered by this definition:

32.4 0.7 2.0 0.0 2.00

(i)

Give an appropriate BNF definition for a positive decimal number, as defined above, defining any terms you introduce.

[4]

<digit> ::= 0|1|2|3|4|5|6|7|8|9
<point> ::= .
<number> ::= <digit> | <digit><number>
<decimal> ::= <number> <point> <number>

(ii)

An alternative to the use of BNF is the syntax diagram.

A syntax diagram is started below for the positive decimal number. Copy and complete this diagram.

7(a)

One method of describing an algorithm is pseudocode.
State two other methods.

[2]

a description written in English
a flowchart

(b)

Quicksort is a very fast sort algorithm.

(i)

The Quicksort algorithm calls itself. What name is given to this type of algorithm.

[1]

recursive algorithm

(ii)

What other feature does this type of algorithm need to have?

[1]

a terminating condition.

Numbers are often stored in computers in floating point form.

(i)

State one benefit of storing numbers in floating point form.

[1]

a greater range of numbers can be represented.

(ii)

State one problem associated with storing numbers in floating point form.

[1]

lack of precision. Some numbers can only be approximated to.

9(a)

Describe the difference between a compiler and an interpreter.

[2]

a compiler translates a high-level language source program into executable machine code
an interpreter translates one line at a time, executing each line as it does so.

(b)

Describe what happens during the following two compilation stages:

(i)

syntax analysis;

[2]

the compiler checks that the rules of syntax of the language have been obeyed.
Syntax errors would be reported.

(ii)

semantic analysis;

[2]

The meaning of the code is analysed and decisions are made how it is to be executed.
The program is converted into a symbol table of numbers.

(c)

Explain the term relocatable code.

[1]

code that can be stored and run at any position in memory.

10.

The following is part of an algorithm:

position = 0
count = 0
     while ((position = 0) and (count < n))
          count = count + 1
          if (value[count] = search_element)
               then position = count
          endif
     endwhile

Initially:

n is set to 4
value[1] is set to 6
value[2] is set to 12
value[3] is set to 15
value[4] is set to 12
search_element is set to 12

(i)

Show the effects of this algorithm by completing the following table. Part of the first line is already filled in.

[3]

n	value[1]	value[2]	value[3]	value[4]	search_element	position	count
4	6	12	15	12

n	value[1]	value[2]	value[3]	value[4]	search_element	position	count
4	6	12	15	12	12
						0	0
						0	1
						0	2
						2	2

(ii)

State the function of this algorithm.

[1]

to find the first position of a number in a list of values.

(iii)

I. What would have been the final value of position, if search_element had been set to 9, with all other variables taking the same values as in part (i)?

[1]

the final value would have been 0

II. Comment on this situation.

[1]

if the number is not in the list then the position will remain with value 0.

11.

In the following question, additional credit (up to 3 marks) will be gained if your answer demonstrates skill in written communication.

Many software tools are available to assist a programmer to develop a large program or suite of programs.

These include compilers for different languages, for instance procedural and non-procedural languages, fourth generation languages, application generators, and visual programming languages. The tools available also include computer aided software engineering (CASE) tools, and debuggers.

Describe in detail the role of each of the items in italics in the above paragraph in assisting the software development process.

[8+3]

High level language programs can be written in a number of different types of languages. Procedural languages (eg PASCAL) are written using an ordered sequence of instructions. Non-procedural languages (eg PROLOG) have a set of defined facts, and rules are used to deduce information from these.

Fourth generation languages such as SQL are based around a database and have facilities for data searching and sorting.

Application generators are programs which create applications from a set of specifications. Visual programming languages (eg Visual Basic) create applications which can be run in a WIMP (Windows) environment.

CASE tools can be used to make program development faster and easier, and may involve graphics tools, interface creation tools, and source code generators for a variety of languages. Eg A COBOL program may be developed from a set of system specifications.

When developing software, debuggers will help to track down any bugs and where the problem can be found. These may include the use of break-points which stop a program at a pre-defined point, single-stepping through a sequence of instructions, and memory dumps which allow the viewing of memory store locations.