Chapter 21 Digital Design Principles

Question 1

What is abstraction?

Answer 1

Abstraction involves removing specific details from a problem that are not needed to solve it.

Question 2

What is decomposition?

Answer 2

Decomposition involves breaking a large, complex problem into smaller sub-problems and then solving each one individually. The small solutions can then be brought together to provide an overall solution to the complex problem.

Question 3

What is the Graphic and Purpose of a Flow Line?

Answer 3

The purpose of a flow line is to indicate the flow of logic and connect the different symbols together. A flow line is displayed as an arrow on a flow chart.

Question 4

What is the Graphic and purpose of a Terminal?

Answer 4

A Terminal (stop/start) represents the start and end of the flowchart. It looks like a rectangle with smooth curves.

Question 5

What is the graphic and purpose of input/output in a flow chart?

Answer 5

Input/output indicates an input or output of data. It is displayed as a parallelogram on a flow chart.

Question 6

What is the graphic and purpose of a process in a flowchart?

Answer 6

A process indicates that an operation is to be done. There is usually text in the box. A process is displayed as a rectangle in a flowchart.

Question 7

What is the graphic and purpose of a decision in a flowchart?

Answer 7

A decision asks a question; there are a number of alternative answers and a pathway is selected based on the response to the question. A decision is displayed as a rhombus in a flowchart.

Question 8

What is the graphic and purpose of a sub-routine?

Answer 8

A sub-routine represents a call to a sub-routine. It is displayed as a rectangle with 1 vertical line through the rectangle near the end of each side of the rectangle.

Question 9

What is the graphic and purpose of a document/report in a flowchart?

Answer 9

A document/report indicates that a report or document is used or produced. It is displayed as a rectangle-like shape; the top of the rectangle is normal but the bottom is sort of curved.

Question 10

What do you use instead of print(“example”) when writing pseudocode?

Answer 10

You write OUTPUT “example”

Question 11

What are the 2 sorting algorithms needed for GCSE?

Answer 11

Bubble sort and insertion sort.

Question 12

How does the bubble sort work?

Answer 12

• Adjacent values are compared; if they are out of sequence, they swap positions.
• At the end of the first pass, the largest value is in the last position in the array.

-Multiple passes are performed before the data is fully sorted.

Question 13

Here are some numbers: 35 38 12 995 13 Solve them using bubble sort.

Answer 13

Pass 1: 35 12 38 13 995
Pass 2: 12 35 13 38 995
Pass 3: 12 13 35 38 995
Pass 4: 12 13 35 38 995

Question 14

How does the insertion sort work?

Answer 14

Each comparison examines two adjacent elements in the array of data. If two adjacent elements are out of sequence, they are swapped and the smaller value is added to the sorted sub-list in the correct order.

At the end of one full pass, the array of data is fully sorted.

Question 15

Explain a disadvantage of Bubble sort.

Answer 15

Inefficiency- bubble sort is inefficient for sorting large amounts of data - the time taken to sort data is related to the square of the number of items to be sorted.

Question 16

What are the advantages and disadvantages of using insertion sort?

Answer 16

Advantage:

Stable- insertion sort retains the old unsorted list.

Disadvantages:

Not flexible - insertion sort can only be used with a partially sorted list.

Memory consumption - insertion sort requires a constant amount of memory as the entire sort occurs in internal memory.

Question 17

What are the two searching algorithms in GCSE?

Answer 17

Linear search and binary search.

Question 18

Explain linear search.

Answer 18

Every data item is examined to see if it matches the target value.

The average number of attempts required to find a target value is half the number of data items.

E.g. it could take on average 10 attempts to find a target value in a set of 20 data items.

Question 19

Explain binary search.

Answer 19

The binary search algorithm is more efficient than the linear search algorithm.

It only works on data that is already sorted.

The binary search starts by finding the middle location in the list (mid-point).

The middle location value is compared to the target value. If the target value is not found, the search determines if the target value is below or above the middle location value.

This process is repeated and the number of items being searched through the ‘search space’ is decreased until eventually there is only one item to be searched through.

In a binary search, the maximum number of attempts required to find a target value is log₂ number of items.

So, to find a target value in a set of 20 data items, the maximum number of attempts would be 4.

Question 20

What is refinement and examples?

Answer 20

It is the process of reviewing the design for a solution and making necessary changes so that the design meets the user’s requirements efficiently and accurately.

Refinements can be made to the design to ensure that the user will receive a product that meets their needs.

Possible refinements can be identified by examining the solution and by using a test plan to test the solution prior to writing the code.

The test plan will specify extreme, valid, invalid and null values to be input.

The test plan is used to test the functionality of the program and the accuracy and appropriateness of the output to be produced from the solution.

Additional refinements can also come from the user if they are a part of the design team.

Question 21

What are data requirements and what interface should they have?

Answer 21

Data requirements are the data that a program or system uses, including data input, information output and any values to be stored temporarily during processing.

Example of some data requirements:

Data item Data Sample Function of
Type valid data data item

1 challenge1 integer 15 Stores the
player’s
challenge 1
score
2 player1 string John Stores
name player 1’s
name

firsttimelogin Boolean true Checks if
the user
has logged
in before.

Question 22

What is dry-run testing?

Answer 22

A dry run is a paper-based exercise that allows the programmer to go through the logic of the solution on a step-by-step basis. The dry run highlights any errors in the logic of the solution.

It can be used at the design or coding stages.

It involves creating a trace table with a list of variables and checking the value of the variables after each line of code has been executed.

This can identify errors in the logic of the design and any omissions and incorrect results.

Question 23

How do you create a trace table needed for dry run testing?

Answer 23

1. Number each line of code or pseudocode.
2. Create a table structure.
3. Create a column for each variable in the section of code.
4. Add an output column to show any output generated from the code.