9. Algorithms and Programs

Question 1

What does the operator DIV do?

Answer 1

Finds the whole number of times a divisor can be divided into a number e.g. 11 DIV 2 = 5

Question 2

What does the operator MOD do?

Answer 2

Finds the remainder when a divisor is divided into a number e.g. 11 DIV 2 = 1

Question 3

What is an algorithm?

Answer 3

An algorithm is a set of organised steps or rules to solve a given problem

Question 4

What is a Boolean?

Answer 4

A binary variable that can have two possible values, true or false

Question 5

What is a string?

Answer 5

A data type used to represent a sequence of characters

Question 6

What is an integer?

Answer 6

A whole number (positive or negative)

Question 7

What is a real value?

Answer 7

Numbers including fractions and decimals

Question 8

What is a character?

Answer 8

A letter, digit, space, punctuation mark or various other symbols

Question 9

What is selection?

Answer 9

Determines which path a program takes when it is running e.g. if statements

Question 10

What is a sequence?

Answer 10

The order in which instructions occur and are processed

Question 11

What is repetition and what are the two types?

Answer 11

The repeated execution of a section of code when a program is running
- count controlled iteration: repeatedly executes a section of code a predetermined fixed amount of times
- condition controlled iteration: repeatedly executes a section of code until a condition is met/no longer met

Question 12

What is a variable?

Answer 12

A named space in memory that can contain a single piece of data, which can change during the execution of a program.

Question 13

What is a constant

Answer 13

A named space in memory that always contains the same value during program execution.

Question 14

What is a variable scope?

Answer 14

It indicates the accessibility of a variable.

Question 15

What is a local variable and what are its advantages?

Answer 15

A variable that only exists until the subroutine in which it was created ends.

advantages:
- subroutines with local variables can be reused in other programs
- easier to debug
- saves memory as it only takes up space when it is needed

Question 16

What is a global variable and what are its advantages?

Answer 16

A variable that exists throughout the entire lifetime of a program’s execution.

advantages:
- can be used anywhere in the whole program
- makes maintenance easier as it only has to be declared once
- can be used for constants

Question 17

What is a subprogram and what are the two types?

Answer 17

A subprogram is a smaller program written within a larger one with the purpose of performing a specific task.

1. Procedures
   A procedure performs a specific task and when it is done, the program continues where it left off.
2. Functions
   Functions work the same way as procedures, but can manipulate data and return a result back to the main program.

Question 18

What are the benefits of using subprograms?

Answer 18

• they are small in size so can be tested and debugged easily
• can be saved as modules and reused in different programs
• can be used repeatedly in a program and only be written out once

Question 19

What is a standard function and what are the benefits of using them?

Answer 19

A standard function is an in built, ready made function, e.g. print()

benefits:
- gone through rigorous testing so they work
- code optimised for maximum performance
- portable
- considerable amount of development time

Question 20

What is a parameter?

Answer 20

An item of data passed from one subroutine to another

Question 21

How does a binary search work?

Answer 21

A binary search takes the midpoint of a set of sorted data and compares it to the search value. If the search value is less than the midpoint, all data after the midpoint is eliminated, and if the search value is more than the midpoint, all data before the midpoint is eliminated. The midpoint of the new set of data is then found and the process is repeated until the midpoint equals the search data, or the end of the data is reached.

Question 22

How does a linear search work?

Answer 22

A linear search takes the first item in a set of data (does not have to be sorted) and compares it to the search value. If the search value is not equal to the item in the current position, then the search value is compared to the next piece of data in the list. This process is repeated until the search value equals the item in the current position, or until the end of the data is reached.

Question 23

What is abstraction in terms of computational thinking?

Answer 23

When a problem is simplified so that only the important and relevant details are considered.

Question 24

What is decomposition in terms of computational thinking?

Answer 24

When a large, complex problem is broken down into smaller, more easily solvable problems.

Question 25

What is a rogue value?

Answer 25

An unexpected value that will cause a loop to end

Question 26

What are self-documenting identifiers?

Answer 26

Variables with sensible names that immediately state their purpose in a program. They help other programmers working on the code to understand the purpose of the variable without extensive annotation.

Question 27

How does passing by reference work when passing parameters?

Answer 27

The memory address of the parameter is passed to the subroutine, rather than the actual value of the data. This may lead to unintended side effects, such as the value of the data being changed by the subroutine. This could unintentionally affect the value of the data in the main program as the value is shared between them.

Question 28

How does passing by value work when passing parameters?

Answer 28

A local copy of the data is created for the subroutine and passed to it. If the value is changed by the subroutine that receives it, the original data remains unchanged. This prevents the original data from being changed in the main program. The local copy of the data is then discarded later.

Question 29

What is compression?

Answer 29

Reducing the amount of file space that a file takes up.

Question 30

What is lossless compression?

Answer 30

When data is compressed without any data being lost.

Question 31

What is run-length encoding?

Answer 31

A form of lossless compression that replaces repeated data with a flag character, followed by the character itself and the number of times it is repeated.
E.g. BBBBBBBBB would become $B9

Question 32

What is Huffman encoding?

Answer 32

A form of lossless compression that assigns each character a unique code, with the most frequently used characters assigned the shortest code and the least frequently use characters assigned the longest code.

Question 33

What is lossy compression and how is it calculated?

Answer 33

When data is compressed by removing some of the data.

compression ratio = original file size / compressed file size

Question 34

What is dry running?

Answer 34

A way of determining the purpose of an algorithm by assigning values to the variables and doing any processing that takes place without translating it into code.

Question 35

What is a trace table?

Answer 35

A table to show the variable values when dry running an algorithm.

Question 36

How does a bubble sort work?

Answer 36

It sorts a list of items by comparing each item to the next and swapping them when necessary. The list will keep being passed through until no more swaps need to be made. As it is guaranteed each time that the largest element will be in its correct place after one pass, the last element does not need to be checked on the next pass and the number of comparisons can be reduced by one on each pass. This method of sorting is inefficient as it is the slowest and performs poorly on large amounts of data.

Question 37

How does an insertion sort work?

Answer 37

Items in a list are grouped into two: sorted and unsorted. With each pass through the list, an item from the unsorted sublist is compared with all items in the sorted list until it is inserted into the correct position. Passes are continually made until no items remain in the unsorted sublist. With each pass made, the number of comparisons decreases by one. The first out of order item is copied into a temporary variable as items are shifted to the right to make room in the sorted sublist, meaning the item would be lost if it were not copied into a variable.

Question 38

How do bubble sorts and insertion sorts compare?

Answer 38

They both pass through the list a similar amount of times, however an insertion sort usually involves fewer comparisons per pass, meaning insertion sorts are generally quicker to execute than bubble sorts, especially on large sets of data.