Year 1 - Decision

Question 1

1.1 How can algorithms be written?

Answer 1

Code, flowcharts, or a set of instructions

Question 2

1.1 What can be used to implement an algorithm?

Answer 2

A trace table

Question 3

1.2 What does the shape of each box in a flowchart tell you about the function?

Answer 3

Oval - Start/End
Rectangle - Instruction
Diamond - Decision

Question 4

1.3 Describe a bubble sort

Answer 4

Compare adjacent items in a list:
- If they are in order, leave them
- If they are not in order, swap them
- After the first pass, the last item will be in the correct place
- When a pass is completed with no swaps, the sort is complete

Question 5

1.3 What is the expression for the maximum number of comparisons in a bubble sort?

Answer 5

(n(n -1))/2

Question 6

1.4 Describe quick sort

Answer 6

Select a pivot and split the items into 2 sub-lists:
- One contains the items less than the pivot
- The other contains the items greater than the pivot
- Select further pivots from within each sub-list and repeat the process

Question 7

1.5 What are the 3 bin packing algorithms? Describe them

Answer 7

First-fit: Items in order listed, place each item in the first available bin

First-fit descending: Sort into descending order, then apply the first-fit algorithm

Full-bin: Use inspection to select items that will fill a bin first. Remaining items packed with first-fit

Question 8

1.5 What are the advantages and disadvantages of first-fit?

Answer 8

+ve - Quick to implement

-ve - Unlikely to lead to an optimal solution

Question 9

1.5 What are the advantages and disadvantages of first-fit descending?

Answer 9

+ve - Usually an optimal solution, easy to implement

-ve - May not find optimal solution, takes a long time

Question 10

1.5 What are the advantages and disadvantages of full-bin?

Answer 10

+ve - Usually an optimal solution

-ve - Difficult especially when numbers are large/awkward

Question 11

1.6 What is the order of an algorithm?

Answer 11

If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the run time by a factor of approximately f(m)/f(n)

Question 12

1.6 What order does bubble sort have? Explain how you get this

Answer 12

A list has n items, the first pass will require (n-1) comparisons, a second pass will require (n-2) comparisons, in the worse case this continues, the total number of comparisons would be:
1+2+3+…+(n-3)+(n-2)+(n-1) = (1/2)(n-1)n = (1/2)n^2 - (1/2)n

Since this is a quadratic expression, bubble sort is taken to have quadratic order

Question 13

1.6 What are the rules for linear, quadratic, and cubic order?

Answer 13

If the size of a problem is increased by some factor k then:
- an algorithm of linear order will take approximately k times as long to complete

• an algorithm of quadratic order will take approximately k^2 times as long to complete
• an algorithm of quadratic order will take approximately k^3 times as long to complete