# 1.3 - Algorithms Flashcards

1
Q

What are the two ways algorithms can be defined?

A
• Flow Charts
• Pseudo Code
2
Q

What shape is the start/stop symbol?

A
• Rounded off rectangle
3
Q

What is represented by a rectangle?

A
• A process
4
Q

What shape is a decision represented by?

A
• A diamond
5
Q

What is represented by a parallelogram?

A
• Input/output
6
Q

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

A
• A circle
7
Q

What do the arrows represent?

A
• The direction of flow
8
Q

What is the use of a variable?

A

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

9
Q

What is the use of a constant?

A

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

10
Q

When are values passed by value?

A

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

11
Q

When are values passes by reference?

A

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

12
Q

What is the difference between a local and global variable?

A

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

13
Q

What is a parameter?

A

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

14
Q

What is the difference between validation and verification?

A
• Validation checks if the data seems right

- Verification checks if the data is accurate

15
Q

What two features of does a recursive algorithm need?

A
• To call itself

- Needs a base case

16
Q

Describe a bubble sort

A
• A pass is made over the data
• Neighbouring items are compared
• Stops when a pass is made with no swaps
17
Q

Describe an insertion sort

A
• 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
18
Q

Describe a quicksort

A
• 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
19
Q

A
• 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
20
Q

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)
A
• Logarithmic
• Linear
• Super Logarithmic
• Polynomial
• Exponential
• Factorial
21
Q

What can big O notation refer to?

A
• Time efficiency

- Memory efficiency

22
Q

How would you analyse an algorithm’s time efficiency?

A
• 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)
23
Q

How would you analyse an algorithm’s memory efficiency?

A
• 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)
24
Q

What is lossless compression and where can it be used?

A

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

25
Q

What is lossy compression and where is it used?

A

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
26
Q

What is the compression ratio?

A

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

27
Q

What is compression/decompression time?

A

The time needed to compress or decompress a file

28
Q

What is the saving percentage?

A

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

29
Q

How is a sound file compressed?

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

What is Huffman encoding?

A

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.