Section 2 - Problem solving and theory of computation

Question 1

What is software?

Answer 1

The name given to any program written for a computer

Question 2

What are the stages in writing software?

Answer 2

Analysis > Design > Implementation > Testing > Evaluation
One phase doesn’t have to be finished before another begins

Question 3

What happens during analysis?

Answer 3

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

Question 4

What happens during design?

Answer 4

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

Question 5

What happens during implementation?

Answer 5

The program code is written

Question 6

What happens during testing?

Answer 6

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

Question 7

What happens during evaluation?

Answer 7

The system is evaluated according to given criteria

Question 8

What is a puzzle’s input?

Answer 8

Something that defines an instance of the puzzle. The instance is either specific or general

Question 9

What is an exhaustive search?

Answer 9

Trying every possible combination of numbers

Question 10

How does a binary search work?

Answer 10

• Look at the middle item of a sorted list and compare it to the term you are looking for. If it is the correct term then stop searching. If it is greater than the item being sought, discard the second half of the list. Else, discard the left half. Repeat until the item is found

Question 11

What is the goal of structured programming?

Answer 11

To improve the clarity and maintainability of programs

Question 12

What programming structures are used in structured programming?

Answer 12

Sequence, selection, iteration

Question 13

What are block-structured languages?

Answer 13

Languages like Python, C# and Pascal. The programs are made up of a series of blocks

Question 14

What is a block?

Answer 14

A section of code consisting of 1 or more statements. Each block should have 1 entry and 1 exit point.

Question 15

What is top-down design?

Answer 15

The technique of breaking down a problem into the major tasks to be performed, before breaking each part down even further into its own self-contained module or subroutine

Question 16

What are the advantages of structured (modular) programming?

Answer 16

• Individual modules can be separately tested
• Modules can be kept in a module library to be reused in other programs
• Large programs can be split into modules that are easier to read, debug and maintain
• Several programmers can work on separate modules, shortening development times

Question 17

What is a hierarchy chart?

Answer 17

A tool used to represent the structure of a program, showing how the modules relate to one another. The chart is depicted as an upside down tree shape

Question 18

What is the downside of a hierarchy chart?

Answer 18

It does not show the detailed program structures required in each module

Question 19

What is an algorithm?

Answer 19

A set of clear and precise steps that produce the correct output for any set of valid inputs. It must always terminate at some point.

Question 20

What are the properties of a good algorithm?

Answer 20

• It should allow for invalid inputs
• It should execute efficiently, in as few steps as possible
• It should be designed in a way that others can understand it

Question 21

What are the most common types of algorithms?

Answer 21

• Internet-related algorithms
• Route-finding algorithms
• Compression algorithms
• Encryption algorithms

Question 22

What is the purpose of internet-related algorithms?

Answer 22

They are used to manage and manipulate huge amounts of data stored on the internet

Question 23

What is the purpose of route-finding algorithms?

Answer 23

They work out the most efficient route to get from A to B. This could be cars on a road or data packets across a network

Question 24

What is the purpose of compression algorithms?

Answer 24

They are used to compress data files so they can be transmitted faster or held in smaller amounts of storage

Question 25

What is the purpose of encryption algorithms?

Answer 25

They encrypt data so even if it is intercepted, it cannot be read

Question 26

What is psuedocode?

Answer 26

A method of expressing the solution in a way that can easily be translated into a programming language

Question 27

How does a bubble sort work?

Answer 27

Go through the array. comparing each item with the one next to it. If greater, switch them. Repeat the process n-1 times, reducing the number of items to be examined by 1 each time

Question 28

What can you do to help interpret a program?

Answer 28

• Read the comments in the program
• Look at the variable names to see if they give any clues
• Follow the steps in the program
• Try a “dry run” with some test data

Question 29

What is the purpose of testing?

Answer 29

To try and uncover undetected errors

Question 30

What data should be chosen to test a program with?

Answer 30

• Normal
• Boundary
• Erroneous

Question 31

What is normal data?

Answer 31

Data within the range you would expect, and the data type you would expect

Question 32

What is boundary data?

Answer 32

Data at the ends of the expected range (or just either side of it)

Question 33

What is erroneous data?

Answer 33

Data that is outside of the expected range and the wrong data type

Question 34

What should you state for each test?

Answer 34

• The purpose of the test
• The expected result
• The actual result

Question 35

What criteria could you evaluate a program against?

Answer 35

• Does it meet the performance criteria?
• Does it always perform as expected?
• Is the system reliable?
• Is the system easy to use?
• Has the system been well documented and is easy to maintain?
• How cost-effective is the system?
• How future proof is the system?

Question 36

What are the 2 steps for computational thinking?

Answer 36

• Formulate the problem as a computational problem
• Try to construct an algorithm to solve the problem

Question 37

What is abstraction?

Answer 37

Removing unnecessary details from a program

Question 38

What is representational abstraction?

Answer 38

A representation arrived at by removing unnecessary details

Question 39

What is abstraction by generalisation?

Answer 39

Abstraction by grouping common characteristics to arrive at a hierarchical relationship of the “is a kind of” type

Question 40

What does abstraction allow us to do?

Answer 40

Separate the physical reality of a problem from the logical view

Question 41

What is procedural abstraction?

Answer 41

Using a procedure to carry out a sequence of steps in order to achieve a task

Question 42

What is functional abstraction?

Answer 42

An additional abstraction that can be applied onto the procedure gotten from procedural abstraction. You disregard the particular computational method.

Question 43

What is data abstraction?

Answer 43

A methodology that enables us to isolate how a compound data object is used from the details of how it is constructed.

Question 44

What is problem abstraction?

Answer 44

Details are removed until the problem is represented in a way that is possible to solve because the problem reduces to one that has already been solved.

Question 45

What is procedural decompostion?

Answer 45

Breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.