2.3.1 Algorithms

Question 1

Define a linear search

Answer 1

Finds an item in a list by checking each item in turn

Question 2

What are the key points of a linear search?

Answer 2

• Starts at the first item
• Searches in sequence
• Can be represented in an array or binary tree

Question 3

What are the advantages of a linear search?

Answer 3

Easy to implement

Works on ordered or unordered lists

Easy to add items

Question 4

What are the disadvantages of a linear search?

Answer 4

Usually most inefficient on longer lists

Question 5

Define a binary search

Answer 5

An algorithm for finding an item in a sorted list.

Starts at the middle and repeatedly divides the list containing the item in half

Question 6

What are the key points of a binary search?

Answer 6

• Starts at the middle item
• Halves the items needed to search after each check
• Can be represented by an array or linked list

Question 7

What are the advantages of a binary search?

Answer 7

Efficient

Suitable for large data sets

Question 8

What are the disadvantages of a binary search?

Answer 8

Only works on ordered lists

Slow to add items, as they must be placed in the right place

Question 9

Define a bubble sort

Answer 9

Orders a list of items by comparing and swapping pairs of items.

It ‘bubbles’ the smallest/largest number to the ends

Question 10

How does a bubble sort work?

Answer 10

• Starts at the first item
• Compares with the adjacent item, swapping if necessary
• Moves on until all pairs have been compared
• If any were swapped then a new pass will start

Question 11

What are the advantages and disadvantages of a bubble sort?

Answer 11

Advantage: works well on small lists

Disadvantage: slow to work

Question 12

Define an insertion sort

Answer 12

Slots each item into the correct position in a data set

Question 13

How does an insertion sort work?

Answer 13

• Compares the second item to the one before
• Will continue along until the current item is less than the one before
• Compares the current item with all before to find the correct location
• Moves the items to their new positon
• Repeats until everything is in position

Question 14

What are the advantages and disadvantages of an insertion sort?

Answer 14

Advantage: works well on small lists

Disadvantage: slow to work

Question 15

Define a merge sort

Answer 15

Uses ‘divide and conquer’ to quickly sort data.

Creates multiple sub-problems, which are each solved individually before being re-joined.

Question 16

How does a merge sort work?

Answer 16

• Repeatedly divides the list in half until each item has its own list
• Compares adjacent lists to order them into a new list
• Removes old lists
• Repeats with adjacent lists until one list formed

Question 17

Define a quick sort

Answer 17

Sorts a set of data at a high speed using ‘divide and conquer’.

It creates sub-programs which are solved individually then combined.

A pivot value will be chosen to compare the items to when dividing the list.

Question 18

How does a quick sort work?

Answer 18

• Sets a pivot value
• Compares each item to the pivot value, adding those less than to one list and greater than to another
• A pivot is chosen for the new lists
• Repeats until each item has its own list
• Conjugates the lists from left to right

Question 19

Define the ‘Dijkstra’s Shortest Path algorithm’

Answer 19

Finds the shortest distance between the starting node and target node using a weighted tree

Question 20

Define the ‘A* algorithm’

Answer 20

Finds the shortest path between two vertices on a weighted tree using heuristics. Won’t consider every vertex

Question 21

What are the advantages and disadvantages of Dijkstra’s Shortest Path?

Answer 21

Advantage:

Finds the shortest time to a location

Disadvantage:

Every vertex must be investigated

Question 22

What are the advantages and disadvantages of the A* algorithm?

Answer 22

Advantages:

Optimal in regards to efficiency

Works well for complex problems

Disadvantages:

The speed of execution is dependant on the heuristic accuracy

Can have complexity problems

Question 23

How is the Dijkstra’s Shortest Path algorithm carried out?

Answer 23

• Two lists are formed: visited and unvisited nodes
• Node distances are infinity, other than the starting node, all fill the unvisited list

1. For the current node: neighbouring unvisited nodes are examined by calculating the total distance to them from the start
2. If the new distance is less than the known distance, the distance and previous node information is updated
3. Add the current node to the visited list and move to the next shortest-distance-away node
4. Repeat until all nodes have been visited

Question 24

How is the A* algorithm carried out?

Answer 24

• Fundamentally the same as Dijkstra’s
• Each node has a heuristic value, e.g. the distance or time to the final node
  
  • The nodes are ordered by heuristic + weight
  • Once the final node has been reached and expanded, unvisited nodes are ignored as the shortest path is found

Question 25

What are the 5 main Big O notations?

Answer 25

Constant: O(1)

Logarithmic: O(log n)

Linear: O(n)

Polynomial: O(n²)

Exponential: O(nⁿ)

Question 26

Explain constant Big O notation and state its time and space efficiency

Answer 26

• Takes the same time to run regardless of the size of inputted data
• Time: good
• Space: good

Question 27

Explain logarithmic Big O notation and state its time and space efficiency

Answer 27

• As the data set size increases, the time execution’s rate of decrease will increase
• Time: good
• Space: good

Question 28

Explain linear Big O notation and state its time and space efficiency

Answer 28

• Time will increase directly proportionally to the size of inputted data
• Time: average
• Space: average

Question 29

Explain polynomial Big O notation and state its time and space efficiency

Answer 29

• Will match every item in the list with every other item: finds all possible combinations. Time execution’s rate of increase will increase with data set size
• Time: average
• Space: average

Question 30

Explain exponential Big O notation and state its time and space efficiency

Answer 30

• The time to complete doubles with each new data item. Works quickly with small data sets, and much longer with larger ones
• Time: bad
• Space: average