D1, C1 - Algorithms

Question 1

What is an algorithm

Answer 1

A process or a set of instructions that need to be followed PRECISELY

Question 2

How can you use a table to implement algorithms (what goes in the top row (headers))

Answer 2

Step number
Variables (such as A, B, et…)
Print (if things are printed)

Question 3

What numbers does an algorithm generate if it generates (1, 1, 2, 3, 5, 8, …)

Answer 3

Fibonacci sequence

Question 4

What is a flow chart

Answer 4

A way of listing instructions or a process

Question 5

What shape is a start / end in a flow chart

Answer 5

Oval

Question 6

What shape is an instruction in a flow chart

Answer 6

Rectangle

Question 7

What shape is a decision (question) in a flow chart

Answer 7

Diamond

Question 8

What is a trace table

Answer 8

A table that record actions / results

Question 9

What goes in the header of a trace table

Answer 9

Actions
Variables
Print
Decisions

Question 10

Perform a bubble sort on 4, 1, 3, 2 to get them into ascending order

Answer 10

1) 4, 1, 3, 2
2) 1, 3, 2, 4
3) 1, 2, 3, 4
4) 1, 2, 3, 4

Question 11

What are the steps for a bubble sort

Answer 11

1) Start at the beginning and move from left to right comparing adjacent items, if in order leave, if out of order swap
2) When you get to the end of the working list, last item will be in its final position, this item is no longer in the working list
3) If you have made some swaps in the last pass repeat step 1
4) When a pass is completed with no swaps, every item is in final position and the list is in order

Question 12

What is ascending

Answer 12

Smallest to biggest

Question 13

What is descending

Answer 13

Biggest to smallest

Question 14

Bubble sort into ascending order:
24, 18, 37, 11, 15, 30

Answer 14

1) 24, 18, 37, 11, 15, 30
2) 18, 24, 11, 15, 30, 37
3) 18, 11, 15, 24, 30, 37
4) 11, 15, 18, 24, 30, 37
5) 11, 15, 18, 24, 30, 37

Question 15

What working should you show with bubble sorts

Answer 15

Circle letters / numbers being swapped
Write swap / leave
Perform a FINAL pass to show nothing changes

Question 16

How do you find the pivot of a quick sort for even and odd n (where n is the number of letters / numbers)

Answer 16

(n + 1) / 2 if n is odd
if n is even round up

Question 17

What are the steps of a quick sort (ascending) (6)

Answer 17

1) Choose the item at the midpoint of the list to be the first pivot ((n+1)/2)
2) Write down all the items that are less than the pivot, keeping their order, in a sub list
3) Write down the pivot
4) Write down the remaining items ( greater than the pivot) in a sub list
5) Apply steps 1 to 4 for each sub list
6) When all items have been chosen as pivots, stop

Question 18

Perform a quick sort on 8, 3, 6, 4, 2 into ascending order

Answer 18

1) 8, 3, (6), 4, 2
2) 3, (4), 2, (6), (8)
3) 3, (2) (4), (6), (8)
4) (2), (3), (4), (6), (8)

Question 19

What are bin packing algorithms

Answer 19

Algorithms that allow us to put different sized items into bins, so that there is the least amount of wasted space and the least number of bins is used

Question 20

What are examples of bin packing uses

Answer 20

Production lines
Files on a hard disk
Packing items into a lorry

Question 21

What is the lower bound in bin packing

Answer 21

The least number of bins required for packing

Question 22

Is the lower bound in bin packing always achievable

Answer 22

NO

Question 23

What does it mean if a solution for bin packing is the lower bound

Answer 23

Solution = optimal solution

Question 24

What is the formula for lower bound in bin packing

Answer 24

Total size of all items / bin size
(round up)

Question 25

What is a first-fit algorithm

Answer 25

Take each item in the order it is given
Place it into the first available bin it will fit

Question 26

Pros and cons of first fit algorithm

Answer 26

+ Easy to implement
- Not likely to be efficient

Question 27

What is a first-fit decreasing algorithm

Answer 27

Sort items into descending order
Apply first fit algorithm

Question 28

Pros and cons of first-fit decreasing algorithm

Answer 28

+ Usually a good solution
- May not be optimal solution

Question 29

What is a full-bin packing algorithm

Answer 29

Put together items that will completely fill a bin
Place any remaining items using first-fit algorithm

Question 30

Pros and cons of full-bin backing algorithm

Answer 30

+ Usually get a good solution
- Difficult to implement

Question 31

What is the equation when time is proportional to number of items (n)

Answer 31

t = kn

Question 32

What is the equation when time is proportional to number of items squared (n^2)

Answer 32

t = kn^2

Question 33

What is the equation when time is proportional to number of items cubed (n^3)

Answer 33

t = kn^3

Question 34

What does the order / complexity / size of problem of an algorithm mean

Answer 34

Whether time is proportional to number of items linear / quadratic / cubed

Question 35

What is the time taken to complete an algorithm also called

Answer 35

Run time

Question 36

What is important about values worked out for run time

Answer 36

They are estimates

Question 37

The bubble sort algorithm has quadratic order. Given that it takes a computer 0.2 seconds to sort a list of 1600 numbers using the bubble sort, estimate the time needed to sort a list of 480,000 numbers

Answer 37

t proportional to n^2
t = kn^2
0.2 = k * 1600^2
k = 7.8125 * 10^-8
t = 7.8125 * 10^-8 * n^2
t = 180,000 seconds
t = 5 hours

Question 38

A bubble sort algorithm has quadratic order, comment on the suitability of the bubble sort algorithm for sorting large data sets

Answer 38

Since the time taken increases by a factor of the number of items squared, this algorithm is NOT suitable for sorting large data sets of items