(GCSE ARCHIVE) Algorithms, Design, and Testing

Question 1

What is structured programming?

Answer 1

Structured programming involves decomposing a program into smaller manageable modules. Each of these modules is then decomposed even further repeatedly until eventually reaching modules that perform specific tasks.

Question 2

What are the advantages of structured programming?

Answer 2

• Coding is easier because you’re only writing subroutines that carry out very simple tasks
• Lots of programmers can work on one program as each module can be written independently.
• It’s easier to test structured programs as each module can be tested individually.
• You will be able to reuse the subroutines and modules in programs you write in the future.
• Individual subroutines and modules can be fixed and updated without affecting the rest of the program.

Question 3

What is authentication?

Answer 3

The process of verifying the identity of a user before they’re allowed to access anything, such as through passwords.

Question 4

Ways of increasing the security of a password-based authentication system

Answer 4

• Limit the number of failed authentication attempts a user can have before locking their account for safety.
• Force users to use strong passwords that cannot be easily guessed.
• Force users to regularly change their passwords.

Question 5

What is input validation?

Answer 5

Checking if data meets certain criteria before passing it into the program. An example would be checked that a phone number only has numbers in it.

Question 6

What are the 5 types of common input validation checks?

Answer 6

• Range checks
• Presence checks
• Format checks
• Length checks
• Look-up table

Question 7

Range check

Answer 7

Checks the data is within a specific range of values.

Question 8

Presence check

Answer 8

Checks that data has actually been entered.

Question 9

Format check

Answer 9

Checks the data has the correct format (e.g. a date).

Question 10

Look-up check

Answer 10

Checks data against a table of acceptable values.

Question 11

Length check

Answer 11

Checks the data is the correct length (e.g. a password must be between 8-20 characters).

Question 12

Ways to improve the maintainability of code

Answer 12

• Only use global variables when necessary, as they could affect the rest of your code (e.g. somebody else uses the same variable name as you).
• Use local variables in subroutines instead, as they don’t affect anything outside of the subroutines they’re in.
• Variables, subroutines, and parameters should be named appropriately, and refer clearly to what they are. This avoids confusion later on and makes it easier to keep track of what each variable does.
• Comments (written after # or //) are useful for explaining the key feature of a program. Clear and well written comments are important to help other programmers understand your program.

Question 13

What are the 2 types of errors in programming?

Answer 13

• Syntax Error: When the compiler/interpreter doesn’t understand something you’ve typed, because it doesn’t follow the rules or grammar of the programming language.
• Logic errors: When the compiler/interpreter is able to run the program, but the program does something unexpected.

Question 14

Why is it harder to find the source of a logic error?

Answer 14

• Syntax errors can be diagnosed by a computer, and they often return the line of code in which a syntax error is found.
• Logic errors aren’t picked up by compilers/interpreters, as the code still follows the syntax. Logic errors are found through systematically testing a program using a test plan.

Question 15

What are the three types of test data?

Answer 15

• Normal data: Typical, sensible data that the program should accept.
• Boundary (extreme) data: Valid or invalid data that is on either side of the boundary of what the program should accept as normal. data.
• Erroneous data: Invalid data that the program should not accept.

Question 16

What are trace tables useful for?

Answer 16

• Trace tables are a simple way of testing that a piece of code is working correctly.
• They keep track of the values of certain variables take as you go through the code.
• Their main use is to ‘dry run’ a subroutine or algorithm to make sure there are no logic errors.
• They can help you to understand what a piece of code is doing.

Question 17

What is time efficiency?

Answer 17

• Many algorithms are made to do the same thing, and each algorithm takes a certain amount of ‘time’ to complete a task.
• Algorithms that take less ‘time’ to complete the task have better time efficiency.
• When programmers talk about the ‘time’ an algorithm takes, they don’t mean real-life time. They measure things like the number of times memory was accessed, the number of CPU cycles taken to execute commands, or the number of times a loop was created.

Question 18

What are the three key techniques for computational thinking?

Answer 18

• Decomposition
• Abstraction
• Algorithmic Thinking

Question 19

What is decomposition? Give one advantage of using this technique.

Answer 19

• The process of breaking down a complex problem down into smaller sub-problems and solving each one individually.
• You can assign different sub-problems to people in a team to solve a large problem faster.

Question 20

What is abstraction?

Answer 20

The process of picking out the important bits of information from a problem, and ignoring all the specific details that don’t matter.

Question 21

What is algorithmic thinking?

Answer 21

Algorithmic thinking is a logical way of getting from a problem to a solution. If the steps you take to solve a problem follow an algorithm, then they can be reused and adapted to solve similar problems in the future.

Question 22

What is a benefit of using pseudocode to write algorithms?

Answer 22

• It clearly shows an algorithm’s steps, and it can be written quickly, without worrying about the syntax of any particular programming language.
• You can write it differently, as long as the person reading it can follow it and understand what you mean.
• You can easily convert it to any programming language.

Question 23

Pseudocode Algorithm: Outputting a person’s salary after a 10% bonus is added to it.

Answer 23

salary <– USERINPUT

newsalary <– salary * 1.1

OUTPUT newsalary

Question 24

Pseudocode Algorithm: When registering on a website, a user’s password should be:

• More than 6 characters long
• Different from their username

Write an algorithm to check the validity of their password, and state why their password is invalid.

Answer 24

username <– USERINPUT

password <– USERINPUT

IF length of password <= 6 THEN

OUTPUT  'Password is too short'

ELSE IF password == username THEN

OUPUT  'Password is the same as username.'

ELSE

OUTPUT  'Password is valid.'

Question 25

What is an algorithm?

Answer 25

A process or logical step-by-step or set of instructions that are used to solve a problem or carry out a task.

Question 26

What is a binary search? Give an advantage and two disadvantages of using this algorithm.

Answer 26

• It is a search algorithm that looks for items in an ordered list.
• It is efficient on larger lists.
• It is harder to implement than other search algorithms as it is more complex.
• It only does not work on unordered lists.

Question 27

How does a binary search work?

Answer 27

1) Find the middle item in the ordered list.

2) If this is target item, them stop the search - you’ve found it.

3) If not, then compare the item to your target item. If it comes before the middle term, get rid of the second half of the list. IIf it comes after the middle term, get rid of the first half of the list.

4) You will be left with a list half the size of the original list, so repeat these steps 1-3 on the new smaller list until you’ve founded the target item.

Question 28

What is a linear search?

Answer 28

• A search algorithm which checks each item in a list, one after the other, to see if it’s the correct one. It stops when the value has been found, or the entire list has been searched.
• It is simple to code, so it is easy to implement
• It works on unordered lists
• It is efficient on smaller lists
• It is inefficient on bigger lists.

Question 29

Which search algorithm is more efficient for small and large lists?

Answer 29

• For small ordered lists the difference in efficiency doesn’t matter much, so the run time of both algorithms is the same.
• For large lists, binary search algorithms a generally much quicker and so have a lower run-time.

Question 30

What is a bubble sort algorithm?

Answer 30

• A sort algorithm that is used to sort an unordered list.
• It is a very simple algorithm, but can often take a while to sort a list.

Question 31

How does bubble sort work?

Answer 31

1) Look at the first two items in a list.

2) If they’re in the right order, you don’t have to do anything. If they’re in the wrong order, swap them.

3) Move on to the next part of items (2nd and 3rd items) and repeat step 2.

4) Repeat step 3 until you get to the end of the list - this is called one pass. The list item in the list will not be in the correct place, so don’t include it in the next pass.

5) Repeat steps 1-4 until there are no swaps in a pass.

Question 32

What are the advantages and disadvantages of bubble sort?

Answer 32

• It is a simple algorithm that can easily be implemented on a computer.
• It is an efficient way to check if a list is already ordered, as you only have to do 1 pass (or n-1 comparisons).
• Doesn’t use much memory, as all the sorting is done using the original list.
• It’s an inefficient way to sort a list.
• Due to being inefficient, it’s very slow for very large lists.

Question 33

What is a merge sort algorithm?

Answer 33

A sort algorithm that is an example of a divide-and-conquer algorithm. It takes advantage of two things:

• Small lists are easier to sort than large lists.
• It’s easier to merge two ordered lists than two unordered lists.

Question 34

How does a merge sort algorithm work?

Answer 34

1) Split the list in half. Each new list is called a sub-list. The second sub-list should start at the middle term (n+1)/2

2) Keep repeating step 1 on each sublist until all the lists contain only 1 item.

3) Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order.

4) Repeat step 3 until all the sub-lists are merged together again, and now you have one complete ordered list.

Question 35

What are the advantages and disadvantages of implementing a merge sort algorithm?

Answer 35

• In general, it’s much more efficient and quicker than bubble sort algorithms for large lists, and has a similar run time for smaller lists.
• It has a very consistent run time, regardless of how ordered the items in the original list are.
• Even if the list is already sorted, it still goes through the whole splitting and merging process, so a bubble sort can be faster in some case.
• It uses more memory than the bubble sort because it has to create new additional sub-lists.