CP4 Computing June 2002

Many companies use software packages to solve problems rather than using a traditional programming language.

(i)

Describe two possible benefits of this package-based approach compared with the use of a programming language.

[2]

the software is already coded and so it will be faster to implement
the programs are already tested and so will definitely work.

(ii)

Describe one drawback of this package-based approach compared with the use of a programming language

[1]

the programs may not have the exact features required by the company - they may not do exactly what is wanted.

R is the six-digit binary number 101010
S is the six-digit binary number 110011

(i)

Write down the effect of carrying out the logical operation R AND S

[1]

100010

(ii)

Write down the effect of carrying out the logical operation NOT R

[1]

010101

3(a)

A stack is a type of data structure.

(i) Explain what is meant by the term data structure.

[1]

a data structure is a method of organising data which allows for efficient processing.

(ii) Explain, using a diagram, the term stack, and outline what should happen when an attempt is made to to remove an item from an empty stack.

[3]

a stack is a LIFO structure - last in first out. When a record is removed, it is always the one that was most recently entered.

a pointer keeps track of where the top of the stack is.

8
7
6
5
4
3	Tomkins
2	Jones
1	Smith

TOS (top of stack) pointer = 3

when an attempt is made to remove an item from an empty stack, the 'top-of-stack' pointer is checked first. If it indicates an empty stack an error message is output. There is no change to the stack pointer.

(iii) When would a stack be used in a computer system?
Why is a stack the most appropriate data structure in this case?

[2]

'return' addresses of subroutines are placed on a stack every time a new subroutine is called..
when a subroutine is finished, the program needs to return to the most recently called subroutine - ie last-in-first-out structure.

(b)

Goodevenings is a company with shops throughout the country which sell the following categories of products:

compact discs;
computer games;
books;
magazines;
board games.

For each of these categories, sales figures for one shop were recorded every month in 2001.

(i) Describe, using a diagram, a suitable data structure for this application.

[2]

A two-dimensional array is needed.(categories / months) showing the sales figures...

	Month
	Jan	Feb	Mar	...
CDs	12	23	18	...
Games	5	7	4	...
Books	12	8	9	...
Magazines	4	12	9	...
Board games	8	10	3	...

(ii) State an appropriate data structure if this system is extended to store sales figures from all the shops in the company.

[1]

a three-dimensional array (categories / months / shops) of sales figures.

4(a)

In a certain 8-bit computer, all integers are stored in binary, and negative integers are stored in two's complement form.

(i) Show how the number +36₁₀ is represented.

[1]

00100100

(ii) Show how the number -12₁₀ is represented.

[2]

12 = 00001100
Take the two's complement and -12 = 11110100

(b)

(i) Describe an advantage to a user of representing numbers in hexadecimal instead of binary.

[1]

smaller numbers, so easier to work with - fewer mistakes

(ii) Convert the binary number 100100011110₂ to hexadecimal.

[1]

(c)

Describe how a character may be represented in binary.

[1]

every character is given a unique numerical code (eg ASCII). The character is stored as the binary equivalent of this code.

(d)

Show the effect of a logical shift right by one place on the following 8-bit number:
10110110.

[1]

01011011

5(a)

There are various types of programming languages.

(i) Describe each of the following types of language, and give an example of a suitable use for the language in each case:

I. a procedural language;

[2]

an ordered sequence of instructions is carried out.
eg used for processing the monthly payroll for a business.

II. a non-procedural language.

[2]

a set of facts is declared and a set of rules is used to make deductions from them.
eg used for AI (artificial intelligence) programs eg an expert system.

(ii) Describe a situation where a special purpose language would be useful and describe why it would be preferable to a general purpose language in this case.

[2]

a special purpose language would be useful for programming embedded systems.
The instructions would be more designed specifically for the processes carried out by the system.

(iii) Describe a situation where a fourth generation language would be useful and describe why it would be particularly suitable in this case.

[2]

useful in programming database processes eg delete all customers who have had no transactions.
the code needed would be small and designed specifically for databases.

(iv) Describe a situation where a visual programming language would be useful and describe why it would be particularly suitable in this case.

[2]

programming a windows (WIMP) application.
the programmers would not need to provide their own code for the windows, scroll bars, buttons etc...so easier and faster programming

(b)

When a programmer is developing a computer program, she uses a variety of computer tools, including computer aided software engineering (CASE) tools and debuggers.

(i) Explain what is meant by the term CASE tool and describe how it will help the programmer.

[2]

A CASE tool is a program which makes it easier for programmers to develop software.
programs which help in the design, scheduling and testing of software projects..which should save the programmers considerable time and effort.

(ii) Describe two facilities available in a debugger.

[2]

tracks down bugs - errors in a program
allows single-stepping - running a program one line at a time looking at the effects on variables etc

6(a)

Backus Naur Form (BNF) is often preferred to English as a means of defining syntax rules. Why is BNF so useful?

[2]

it defines syntax terms in a simple structured way, which allows unambiguous parsing of expressions.
it allows recursive definitions.

(b)

A certain program needs to have a definition of what is meant by a command word.

The definition is as follows:

A command word...

must be made up of letters and digits only;
must begin with a letter.

Produce an appropriate Backus Naur Form (BNF) definition for a command word.

[4]

<letter> ::= A|B|C|D|E|F|G|H.....|X|Y|Z|a|b|c|d|.....|x|y|z
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<character> ::= <letter> | <digit>
<word> ::= <character> | <character> <word>
<command word> ::= <letter> | <letter><word>

7(a)

Explain what is meant by the term algorithm.

[2]

an ordered sequence of steps....
... used to solve a problem or complete a process.

(b)

State two methods of describing algorithms.

[2]

a flowchart
pseudocode

(c)

(i) Describe the key features of a recursive algorithm.

[2]

it 'calls' itself
there is a terminating condition.

(ii) Describe one advantage of a recursive algorithm when available.

[1]

more concise code leading to simpler solutions and smaller programs.

8(a)

Describe the following stages of the compilation process:

(i) lexical analysis;

[2]

comments and spaces are removed,
the program is converted into a numerical symbol table

(ii) syntax analysis.

[2]

parsing takes place to check the rules of syntax have not been broken.
error messages are output if necessary.
a 'dictionary' of variables is created.

(b)

Describe the function of a linking loader.

[1]

previously compiled code is loaded into the correct place in memory, and connections to it are established.

Consider the following algorithm.

Line
1	repeat
2	finished := TRUE
3	for i := 1 to n-1
4	if value[i] <= value[i+1]
5	temp := value[i+1]
6	value[i+1] := value[i]
7	value[i] := temp
8	finished := FALSE
9	endif
10	endfor
11	until finished = TRUE

(i)

What is the function of this algorithm?

[1]

to bubble sort a list of values into descending order.

(ii)

What will be the effect of the algorithm if:

n=5
value[1] = 3
value[2] = 4
value[3] = 2
value[4] = 6
value[5] = 10 ?

[1]

value[1] = 10
value[2] = 6
value[3] = 4
value[4] = 3
value[5] = 2

(iii)

The algorithm will fail if:

n=5
value[1] = 3
value[2] = 6
value[3] = 2
value[4] = 6
value[5] = 10

I. Describe what feature of the data will make the algorithm fail in this case.

[1]

there are two values the same.

II. What will happen when the data is used?

[1]

the algorithm would never finish - it would swap the two identical values on every pass and 'finished' would never become 'TRUE'

III. What alteration to the algorithm will ensure the algorithm works correctly for this data?

[1]

Line 4 : '<=' needs to be changed to '<'

10.

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

When a new computer system is designed, considerable attention is paid to the design of the human computer interface (HCI). Various approaches are possible, for instance, in the use of text based or graphical user interfaces, speech recognition and handwriting recognition, and speech synthesis. In some cases a natural language interface is also employed.

Describe the issues involved in the design of the HCI, with reference to the terms shown in italics (green) above. You should include a description of how the design of the HCI should be evaluated.

[9+3]

The HCI needs to be designed to suit the IT skills of the users and the environment where the computer will be used needs to be considered - will it be noisy, dark, etc.

Text-based interfaces offer the most options but the user will need to know the commands required and must enter them with no spelling mistakes. Each command may have a number of options ('switches') available. Eg the DIR command may be entered with a switch DIR /W to opt for a wide-screen display.

Graphical user interfaces (GUIs) are more appropriate for less-skilled users. The use of meaningful icons and a mouse to select them offers an intuitive and 'user-friendly' approach.

Speech recognition systems allow the user to speak commands into microphones. The operating system then interprets the sound received and acts accordingly. There are many problems with this method as users speak differently (different accents, languages etc) and would not be usable in a noisy environment such as a busy office. Any output may be given as speech through speakers using speech synthesis.

Natural language interfaces enable a person to speak to the computer as if it was another person and issue commands to it. Although this is the most 'user-friendly' approach it is not reliable as language is complex and diverse and a globally usable system is difficult to develop.

Handwriting recognition systems require the user to write on the screen or a pad, but people's handwriting also varies considerably so these systems are not generally reliable.

The evaluation of a HCI should be done by asking the users whether they found the system easy to use and error-free, or ,if there were alternative methods, how many users used which system.