Modelling With Algorithms

Question 1

Key points of algorithms

Answer 1

• set of instructions
• finite number of steps
• must work for any input
• must have an end

Question 2

How can algorithms be written?

Answer 2

As text
As a flowchart
As pseudocode

Question 3

What are some key points for algorithms using pseudocode?

Question 4

How do we compare how well algorithms work?

Answer 4

• the efficiency of an algorithm measures ‘run time’ and is usually proportional to the number of calculations that need to be carried out
• the size of the problem is a measure of complexity so in the case of sorting algorithms it’s likely to be the number of elements in the list
• the complexity of an algorithm measures efficiency as a function of the size of the problem. Complexity is indicated by the ORDER

Question 5

What are the different methods for bin packing?

Answer 5

• Full bin algorithm where we look for combinations that make full bins
• First fit algorithm, where we put boxes into bins first fit in the order that they are already in starting from the first bin every time
• first fit descending

Question 6

What are some qualities of first fit algorithm?

Answer 6

• heuristic (solves the problem but doesn’t find an optimal solution)
• easy to carry out or program
• can be inefficient
• systemic approach

Question 7

What are some qualities of the bin packing algorithm?

Answer 7

• can be used in real life contexts (cutting a length of wood, parking vehicles in ferry lanes)
• not guaranteed to give optimal solution
• first fit decreasing is often more efficient than first fit
• must remember to check from first bin onwards with each new item

Question 8

When are sorting algorithms used?

Answer 8

• when we want to sort a list of numbers into ascending order or words into alphabetical order
• we may do this when we require a sorted list E.g to use first fit decreasing algorithm

Question 9

What is the quick sort algorithm?

Answer 9

Step 1: Select the pivot element (first element) from the list
Step 2: Write down all of the numbers that are smaller than the pivot in a sub-list to the left of the pivot, keeping the numbers in their original order. Write down all of the numbers that are larger than the pivot in a sub-list to the right of the pivot, keeping the numbers in their original order.
Step 3: Apply steps 1 and 2 to each separate sub-list until each sub-list contains only one number.

Question 10

Look at Goodnotes for formulae and diagrams

Answer 10

:)

Question 11

What are the dots and lines called in a graph?

Answer 11

Dots: nodes or vertices
Lines: arcs or edges

Question 12

What is a graph?

Answer 12

A series of nodes/vertices connected by edges/arcs

Question 13

How do you find the degree/order of a vertex?

Answer 13

Count how many ends of edges there are at the vertex

Question 14

How do you know if a graph is impossible to draw?

Answer 14

Total order is odd

Question 15

What is a loop

Answer 15

An edge that starts and ends at the same vertex