Unit 2 - Problem solving and theory of computation

Question 1

What is Structured programming?

Answer 1

Structured programming is a method of writing a computer program which uses:
Top-down analysis for problem-solving.
Modularization for program structure and organisation.
Structured code for the individual modules.

Question 2

What is top-down analysis?

Answer 2

The program is divided into modules, which are called from the main program.
Any of the modules may be further broken down into smaller sub-tasks, with the smallest modules performing a single function.
A hierarchy chart may be used to show the overall program structure.

Question 3

How does a hierarchy chart work?

Answer 3

Execution takes place from left to right, always at the lowest level component.
Selection and iteration are not shown in a hierarchy chart.
Any module shown below another module is part of the module above.

Question 4

What are some benefits of structured programming?

Answer 4

Programs are more easily and quickly written:
Large programs are broken down into subtasks that are easier to program and manage.
Each module can be individually tested.
Modules can be re-used several times in a program.

Programs are more reliable and have fewer errors:
It is easier to find errors in small self-contained modules.

Programs take less time to test and debug.

Programs are easier to maintain:
A well-organised, modular program is easier to follow
It is easier to find which module needs to be changed
Self-contained modules mean that the change should not affect the rest of the program.

Question 5

What is modular programming?

Answer 5

Subdividing a computer program into separate sub-programs

Question 6

Why do we use modular programming?

Answer 6

Modular design and programming techniques are most useful for large, complex programs.
Some programs have thousands or even millions of lines of code.

Question 7

What is the aim of structured programming?

Answer 7

Can be thoroughly tested and proved to be error free.
Are easy to understand and maintain.
Minimise duplication of effort.

Question 8

Why are hierarchy charts used?

Answer 8

They’re a useful design tool for breaking down a large program into manageable chunks.
They’re useful for documentation purposes.

Question 9

What is computational thinking?

Answer 9

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

Question 10

What are some methods of problem solving?

Answer 10

Simulation
Enumeration – list all cases
Trial and error
Theoretical approach
Creative solution

Question 11

What is simulation?

Answer 11

The process of designing a model of a real system in order to understand the behaviour of the system, and to evaluate various strategies for its operation.

Question 12

What are the properties of a good algorithm?

Answer 12

Has clear and precisely stated steps that produce the correct output for any set of valid inputs.
Should allow for invalid inputs.
Must always terminate at some point.
Should execute efficiently, in as few steps as possible.
Should be designed in such a way that other people will be able to understand it and modify it if necessary.

Question 13

What are some useful tools for designing algorithms?

Answer 13

Hierarchy charts – useful for identifying the major task, and breaking these down into subtasks

Flowcharts – useful for getting down initial ideas for individual subroutines

Pseudocode – will translate easily into program code

Question 14

What are some examples of sorting algorithms?

Answer 14

Bubble sort and Merge sort.

Question 15

How does bubble sort work?

Answer 15

To sort an array of n items, n-1 passes are made through the array, with each item being compared with the adjacent item and swapped if necessary.

Question 16

What does ‘divide and conquer’ mean?

Answer 16

This involves finding a solution to a sequence of smaller, related problems until the instance is small enough to be solved directly.

Question 17

How does a merge sort work?

Answer 17

Divide the unsorted list into n sublists, each containing one element
Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This is the sorted list.
An example of a ‘divide and conquer’ algorithm.

Question 18

What are some examples of searching algorithms?

Answer 18

Linear search and binary search.

Question 19

How does a linear search work?

Answer 19

Starts at the beginning of the list and examines every item.

Question 20

How does a binary search work?

Answer 20

Uses the “divide and conquer” strategy to halve the search area each time an item is examined.
Can only be used if the list is ordered.

Question 21

What is the purpose of testing?

Answer 21

The purpose of testing software is to reveal errors.
A good test is one which uncovers an error in the program.

Question 22

What are the different stages of testing?

Answer 22

Module testing
Program testing
System testing

Question 23

What does module testing do?

Answer 23

Make sure each subroutine works correctly.

Question 24

What does Program testing do?

Answer 24

Make sure each program in the system works correctly.

Question 25

What does system testing do?

Answer 25

Make sure the whole system works as expected, and does what the original specification required.

Question 26

What is normal data?

Answer 26

Typical, sensible data that the program should accept and be able to process.

Question 27

What is boundary data?

Answer 27

Valid data that falls at the boundary of any possible ranges, sometimes known as extreme data.

Question 28

What is erroneous data?

Answer 28

Data that the program cannot process and should not accept.

Question 29

What is information hiding?

Answer 29

Means
hiding design details behind a
standard interface.

The process of hiding all details of an object that do not contribute to its essential characteristics.

Question 30

What is abstraction?

Answer 30

Removing unnecessary details of a problem to make it more manageable and easier to solve.

Question 31

What is representational abstraction?

Answer 31

An abstraction arrived at by removing unnecessary details.

Question 32

What is abstraction by generalisation?

Answer 32

Means grouping by common characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.

Question 33

What is automation in terms of abstraction?

Answer 33

Refers to building models of real world objects or phenomena in order to solve a particular problem.

Question 34

What is procedural abstraction?

Answer 34

Refers to the mechanisms in computer programming that enable and enforce the abstraction of operations.

Question 35

What is functional abstraction?

Answer 35

Referring to the practice of identifying and expressing a task, or function, in a manner that separates what the task accomplishes from how it’s accomplished.

Question 36

What is data abstraction?

Answer 36

A specific type of abstraction that involves simplifying data structures in order to make them easier to work with.

Question 37

What is problem abstraction?

Answer 37

Details are removed until it becomes possible to represent the problem in a way that is possible to solve.

Question 38

What is procedural decomposition?

Answer 38

Breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task.

Question 39

What is composition?

Answer 39

The opposite of decomposition.
It is the process of combining procedures to form a compound procedure.

Combining data objects to form compound data objects such as a tree or stack.

Question 40

What is a finite state machine?

Answer 40

It is an abstract representation of how something changes from one state to another in response to a condition or event.

Question 41

What is a transition in a finite state machine?

Answer 41

A change from one state to another in response to an event or condition.

Question 42

What are some applications of FSM’s?

Answer 42

Robotics.
Video games industry.
Design of digital hardware systems.
Design of compilers and network protocols.

Question 43

What is a finite state automaton?

Answer 43

A FSM which has no output.
They have an initial state and one or more accepting or goal states.
It simply runs through the input sequence of symbols, one by one, changing state or not as a result of the current state
and the current symbol from the input it sees.
On reaching the end of the input, it stops and, depending on which state it stopped in, accepting state or a non-accepting state, it is able to decide whether the input sequence has met the criteria or not - accepted or not accepted.

Question 44

How can you avoid a FSM having to report an error?

Answer 44

Ensure that for each state there is an outgoing transition for every symbol in the machine’s input alphabet.

Question 45

What is a state transition table?

Answer 45

A state transition table shows the effect of particular inputs on the
current state of an FSM with no output.

Question 46

Why are finite state machines useful?

Answer 46

Finite state machines (FSMs) are used extensively in applications in computer science. For example, finite state machines are the basis for
* Any kind of controller, e.g. traffic lights
* Specifying a language, e.g. given any string, an FSM determines if
that string is in the language or not
* Programs for:
– spell checking
– grammar checking
– indexing or searching large bodies of text
– recognising speech
– processing text containing mark-up languages such as XML
and HTML
* networking protocols that specify how computers communicate.