1.3 - Algorithms

Question 1

What are the two ways algorithms can be defined?

Answer 1

• Flow Charts
• Pseudo Code
• Structured English (Additional)

Question 2

What shape is the start/stop symbol?

Answer 2

• Rounded off rectangle

Question 3

What is represented by a rectangle?

Answer 3

• A process

Question 4

What shape is a decision represented by?

Answer 4

• A diamond

Question 5

What is represented by a parallelogram?

Answer 5

• Input/output

Question 6

What shape is a connector (jump from one point in the sequence to another) represented by?

Answer 6

• A circle

Question 7

What do the arrows represent?

Answer 7

• The direction of flow

Question 8

What is the use of a variable?

Answer 8

A variable is a named area of memory used to store data that may change when the program is running

Question 9

What is the use of a constant?

Answer 9

A constant is a named area of memory used to store data which will not change

Question 10

When are values passed by value?

Answer 10

This is where only the value of the data is passed and therefore it cannot be accidentally changed by the procedure

Question 11

When are values passes by reference?

Answer 11

This is where the memory address of the data is passed and therefore the procedure can update the its value

Question 12

What is the difference between a local and global variable?

Answer 12

Global variables can be changed anywhere in the program whereas local variables be used in the procedure where it is declared

Question 13

What is a parameter?

Answer 13

A parameter is a variable / value that can be passed to / from the procedure

Question 14

What is the difference between validation and verification?

Answer 14

• Validation checks if the data seems right

- Verification checks if the data is accurate

Question 15

What two features of does a recursive algorithm need?

Answer 15

• To call itself

- Needs a base case

Question 16

Describe a bubble sort

Answer 16

• A pass is made over the data
• Neighbouring items are compared
• Swaps made if necessary
• Stops when a pass is made with no swaps

Question 17

Describe an insertion sort

Answer 17

• An unsorted item is compared with the sorted part of the list
• Items in the sorted list are shifted to make room for the new item
• Process continued until the data is sorted

Question 18

Describe a quicksort

Answer 18

• The middle of the list is a pivot
• Two sub-lists are created one less than pivot, one greater than pivot.
• Two more pivots are chosen in each sub list and process is repeated
• Continued until all items are pivoted and list is sorted

Question 19

Give an advantage and disadvantage of recursion

Answer 19

• Some problems can be coded more compactly using recursion
• Less efficient than non-recursive algorithms
• Difficult to debug as you don’t know which recursive cell produced the error

Question 20

Put these into order from most efficient to least efficient:

• O(n log n)
• O(n!)
• O(n^c)
• O(log n)
• O(n)
• O(c^n)

Answer 20

• Logarithmic
• Linear
• Super Logarithmic
• Polynomial
• Exponential
• Factorial

Question 21

What can big O notation refer to?

Answer 21

• Time efficiency

- Memory efficiency

Question 22

How would you analyse an algorithm’s time efficiency?

Answer 22

• Look for the number of calculations / operations
• Each has a value of 1
• If the calculation is inside a loop, it is multiplied by how many time that loop runs in terms of n
• In terms of n, find out how many calculations occur in the whole algorithm
• As n increases, the highest power of n dominates
• Therefore O(n^c)

Question 23

How would you analyse an algorithm’s memory efficiency?

Answer 23

• Look at the number of variables / constants declared
• Constants and variables have a value of 1
• 1D arrays have a value of n
• 2D arrays have a value of n^2
• And so on…
• Overall the highest power of n dominates there for O(n^c)

Question 24

What is lossless compression and where can it be used?

Answer 24

This is where no data is lost when compressing the file instead the data is stored more efficiently to reduce the file size
- e.g A word document

Question 25

What is lossy compression and where is it used?

Answer 25

This is where data is removed from a file to reduce its size. It does this by discarding detail that humans can’t notice or data that that it doesn’t need to make sense.

• Images
• Audio
• Video

Question 26

What is the compression ratio?

Answer 26

This is the ratio of the original file size to the new compressed file size.

Question 27

What is compression/decompression time?

Answer 27

The time needed to compress or decompress a file

Question 28

What is the saving percentage?

Answer 28

A percentage measure of how much smaller the compressed file is to the original file.

Question 29

How is a sound file compressed?

Answer 29

• Discarding sounds that humans can’t hear as when two sounds are playing, we only hear the louder one
• Decrease the sample rate

Question 30

What is Huffman encoding?

Answer 30

It is a dictionary encoding method which stores all the characters that are used in a text, the more commonly used characters are given a shorter code. These codes are then used in the composition of the file. this reduces the file side as the character code is smaller than the ASCII value.