2.2.2. Computational Methods

Question 1

What is meant by a computable problem?

Answer 1

a problem that can be solved using an algorithm, must be solvabel is finite, reasonable period of time and will usually have imputs, outputs and calculations

Question 2

What are 3 limiting factors to computable problems?

Answer 2

time
computer memory
processing power

Question 3

What are 2 factors which may be considered during the problem definition phase?

Answer 3

1. strengths and weaknesses to the current solution
2. types of inputs/outputs and stored data

Question 4

What is the name given to the process where problems are continually broken down until each subproblem can be represented as a subroutine?

Answer 4

problem decomposition

Question 5

What are 3 purposes of problem decomposition?

Answer 5

1. sections can be developed in parallel
2. to identify sections which can make use of pre-coded modules or libraries
3. to simplify testing and maintenance

Question 6

How does divide and conquer technique work? (3 steps)

Answer 6

1. the problem size is halved with every iteration
2. each individual subproblem is then solved recursively
3. the solutions to the subproblem are then recombined to form the final solution to the problem

Question 7

What are 3 applications of divide and conquer?

Answer 7

merge sort
quick sort
binary search

Question 8

What type of programming construct do many problems using divide and conquer use?

Answer 8

recursion

Question 9

What type of abstraction is used to group together sections of problems based on their functionality?

Answer 9

abstraction by generalisation

Question 10

What are 3 problem solving techniques?

Answer 10

pipelining
abstraction
divide and conquer
backtracking
visualitation
data mining
heuristics

Question 11

How does the backtracking algorithm work? (2 steps)

Answer 11

by methodically visiting each path and building a solution based on the paths to be correct
if a path is found to be invalid at any point, it backtracks to the previous stage and visits an alternate path

Question 12

When might heuristics be used in problem solving?

Answer 12

when the standard way to solve the problem is unreasonably time-consuming or resource-intensive (intractable)

Question 13

What are 3 advantages of using performance modelling?

Answer 13

safe
relatively inexpensive
less time-consuming

Question 14

What is pipelining? (2 things)

Answer 14

a process where tasks are developed in parallel
in pipelining, the output of one process becomes the input of another, resembling a production line