2. problem solving and theory of computation

Question 1

computational thinking

Answer 1

the ability to think logically about a problem and apply techniques for solving it

Question 2

pseudo-code

Answer 2

a human-readable method of writing the steps of an algorithm without any particular programming language

Question 3

software

Answer 3

is the name given to any program written for the computer

Question 4

analysis

Answer 4

the requirements and goals of the project must be established, and a data model created. the needs of the end user are considered, and alternative solutions to the problem may be suggested

Question 5

design

Answer 5

data structures will be specified, algorithms, user interfaces, screen designs and reports will all be designed

Question 6

implementation

Answer 6

the program code is written

Question 7

testing

Answer 7

the whole system must be tested for the presence of errors, using selected test data covering normal, boundary and erroneous data

Question 8

evaluation

Answer 8

the system is evaluated according to given criteria

Question 9

exhaustive search

Answer 9

trying every possible combination of numbers

Question 10

binary search

Answer 10

1. look at the middle item of the list first. if this is the item being sought, stop searching
2. otherwise, if the middle item is greater than the one being sought, the item you are looking for must be in the first half of the list so you can discard the second half. otherwise discard the first half of the list
3. repeat with the new list until the item is found

Question 11

the structures programming approach

Answer 11

aims to improve the clarity and maintainability of programs

Question 12

sequence

Answer 12

one statement following another

Question 13

block-structured langauges

Answer 13

e.g. python, pascal, and c#

allow the use of just 3 types of control structure

Question 14

structured programming

Answer 14

important aspect - is to keep subroutines independent of the program which calls them, which means that they should not make use of global variables.

any variable declared in the main program should be passed as a parameter to a subroutine if it is needed.

Question 15

top-down design

Answer 15

is the technique used of breaking down a problem into the major tasks to be performed; each of these tasks is then further broken down into separate subtasks, and so on until each subtask is sufficiently simple to be written as a self contained module or subroutine.

basically “very useful method of breaking down the problem into small, manageable tasks”

Question 16

advantages of structured (modular) programming

Answer 16

• individual modules can be separately tested
• modules can be kept in a module library and reused in other programs
• large programs can be split into modules that are easier to read, debug and maintain
• several programmers in a team can work on separate modules, thus shortening development time for a large project

Question 17

hierarchy charts

Answer 17

is a tool for representing the structure of a program, showing how the modules relate to each other to form the complete solution

Question 18

limitations of hierarchy chart

Answer 18

• does not show the detailed program structure in each module e.g. does not show selection and iteration

Question 19

algorithm

Answer 19

• it has clear and precise stated steps that produce the correct output for any set of valid inputs
• it must always terminate at some point

Question 20

good algorithm properties

Answer 20

• it should only allow for valid inputs
• it should execute efficiently, in as few steps as possible
• it should be designed in such a way that other people will be able to understand it and modify it if necessary

Question 21

what kinds of problem are solved by algorithms

Answer 21

• internet-related algorithms
• route-finding algorithms
• compression algorithms
• encryption algorithms

Question 22

internet-related algorithms

Question 23

route-finding algorithms

Question 24

compression algorithms

Question 25

encryption algorithms

Question 26

divide and conquer

Answer 26

solving a large problem by breaking the problem into smaller sub-programs.

1/2 the search area ???

Question 27

bubble sort

Answer 27

• go through the array, comparing each item with the one next to it. if it is greater, swap them
• the last item in the array will be in the correct place after the place after the first past
• repeat n -1 times, reducing by one on each pass, the number of items to be examined

Question 28

evaluating a problem

Answer 28

one a program has been written and tested, you need to be able to:

• articulate how it works
• produce test data and results to show that it works correctly
• get user feedback to show that nothing has been omitted, that is performs all the required tasks and does so efficiently

Question 29

testing disadvantage

Answer 29

• complex
• time consuming

Question 30

purpose of testing

Answer 30

is to try and uncover undetected errors

Question 31

normal data

Answer 31

is data in range that you would expect, and the data type (real, integer, string etc) that you would expect.

e.g. if you are expecting an input between 0 and 100, you should test 1 and 99

Question 32

boundary data

Answer 32

is data at the ends of the expected range or just either side of it

e.g. -1, 0, 1, 99, 100, 101. test 0 and 100 to make sure that these give the expected results if the valid range is between 0 and 100.

Question 33

erroneous data

Answer 33

is data that is either outside an expected range

e.g. -1, 101, or is of the wrong data type e.g. non-numeric characters when you are expecting a number to be input

for each test you should specify the purpose of the test, the expected result and the actual result

Question 34

evaluation criteria

Answer 34

• does it always perform as expected ?
• is the system reliable or does it crash at intervals?
• is the system easy to use ?
• has it been well documented ?
• will it be easy to maintain ?
• how cost effective is the system - will it increase income, decrease costs, or both ?

Question 35

procedure

Answer 35

the result of abstracting away the actual values used in any particular computation is a computational pattern or method

Question 36

thinking how a problem can be solved involves two basic steps:

Answer 36

• formulate the problem as a computational problem - state it in such a way that it is potentially solvable using an algorithm
• try to construct an algorithm to solve the problem

Question 37

representational abstraction

Answer 37

can be defined as representation arrived at by removing unnecessary details.

Question 38

data abstraction

Answer 38

the storage and representation of data in a computer system along with its logical description and interaction with operators. this allows the construction of new compound data objects from existing ones.

Question 39

example of abstraction

Answer 39

• any computer model, say of environment, a new car or a flight stimulator, is an abstraction…

Question 40

procedural abstraction

Answer 40

simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters.

or using a procedure to carry out a sequence of steps for achieving some task such as calculating a student’s grade from her marks in three exam papers.

Question 41

functional abstraction

Answer 41

simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.

Question 42

information hiding

Answer 42

is where data is not directly accessible and can only be accessed through defined procedures/functions.

e.g. in a class where the data or attributes of the class are private and can only be accessed through public functions.

Question 43

decomposition

Answer 43

is breaking down a complex problem into a number of sub-programs, each of which performs an identifiable task

Question 44

composition

Answer 44

combining small simple procedures to form compound complex procedures

Question 45

problem abstraction

Answer 45

removing small details until the problem is represented in a way that it is possible to solve because it reduces to one that has already been solved

Question 46

automation

Answer 46

the process of creating algorithms and implementing them as data structures and models of real-life situations that run without the significant need for human intervention

Question 47

finite state machine

Answer 47

a model of computation used to design computer programs and sequential logic circuits.

Question 48

in a finite machine

Answer 48

• the machine can only be in one state at a time
• it can change from one state to another in response to an event or condition; this is called a transition. often this is a switch or a binary sensor
• the finite state machine (FSM) is defined by a list of its states and the condition for each transition

Question 49

use of finite machines

Answer 49

can be used in modelling design of hardware digital systems, compilers and network protocols.

they are also used in the definition of languages, and to decide whether a particular word is allowed in the language.

Question 50

fsm with no output

Answer 50

is also known as a finite state autorotation

Question 51

page 61

Answer 51

notation symbols

Question 52

alternative representation of fsm

Answer 52

state transition table