Algorithms

Question 1

binary search precondition

Answer 1

the list needs to be sorted

Question 2

Insertion sort

Answer 2

works by dividing a list into two groups: sorted and unsorted. Elements are inserted one by one into their correct position in the sorted section.

Question 3

linear search

Answer 3

starts at the beginning of a list and checks each item in turn until the desired item is found

Question 4

Binary search

Answer 4

divides a list in two each time until the item being searched for is found

Question 5

Four sorting algorithms

Answer 5

Bubble, Insertion, Quick, Merge

Question 6

Insertion sort words

Answer 6

Make the first item in the list the sorted list. The remaining items are the unsorted list.
While there are items in the unsorted list take the first item of the unsorted list.
While there is an item to the left of it which is smaller than itself swap with that item. End while.
The sorted list is now one item bigger.
End while

Question 7

Merge sort

Answer 7

splits a list of size n into n lists of size 1. Each pair of lists are merged together in order until there is only one list of size n.

Question 8

Why does merge split down into unit lists

Answer 8

because a list of length one is sorted

Question 9

Merge algorithm

Answer 9

1. If the sub-list is 1 in length, then that sub-list has been fully sorted
2. If the list is more than 1 in length, then divide the unsorted list into roughly two parts. (An odd numbered length list can’t be divided equally in two)
3. Keep dividing the sub-lists until each one is only 1 item in length.
4. Now merge the sub-lists back into a list twice their size, at the same time sorting each items into order
5. Keep merging the sub-lists until the full list is complete once again.

Question 10

Quick sort algorithm

Answer 10

REPEAT:
1. Pick a pivot
2. sort the items either side of the pivot
3. make the items either side of the pivot a sublist
Until length of sublist= 1

Question 11

Quick sort

Answer 11

The basic idea is to keep splitting a list into two smaller lists, sort those lists using the same quick-sort rules, then split the sub-lists and sort again, until there are only lists of 1 item or less left.

Question 12

Where can the pivot be applied

Answer 12

The pivot can be applied to any item in the unsorted list.

Question 13

advantages bubble

Answer 13

• simple

Question 14

disadvantages bubble

Answer 14

• long time to run

Question 15

advantages insertion

Answer 15

• Simple to code
• Good performance with small lists
• memory efficient
• good with sequential data

Question 16

disadvantages insertion

Answer 16

• poor performance with larger lists

- not as quick as merge/quick sort

Question 17

disadvantages quick

Answer 17

• difficult to implement
• if a bad pivot is picked the runtime is slow
• worst case efficiency is bad

Question 18

advantages quick

Answer 18

• very efficient

- no additional storage required/ less stack memory

Question 19

advantages merge

Answer 19

• Good for sorting slow access data
• Good for sorting sequential data
• if there are two equal values then positions are conserved, which is quicker

Question 20

disadvantages merge

Answer 20

• It needs twice then length of memory space than the list
• If recursion is used, it used twice the stack memory as a quick-sort
• quick sort is faster

Question 21

advantages Linear search

Answer 21

• Good Performance
• List does not need to be ordered
• Not affected by insertions and deletions

Question 22

disadvantages linear search

Answer 22

• May be too slow over large lists

Question 23

advantages binary search

Answer 23

• Works well with larger lists

- Quicker

Question 24

disadvantages binary search

Answer 24

• Small lists simpler to use linear search

- Cannot deal with unordered lists

Question 25

Shortest path algorithms

Answer 25

Dijkstras and A*

Question 26

Dijkstras table columns

Answer 26

visited, vertex, shortest distance from start node, previous vertex

Question 27

What are all the shortest distances filled with at the beginning (Dijkstras)

Answer 27

infinity, except for the vertex your measuring from which is zero

Question 28

A*

Answer 28

A variation of Dijkstras that uses a heuristic to try and get the correct solution sooner

Question 29

A* table

Answer 29

visited, vertex, shortest distance from start node, heuristic distance, sum, previous vertex

Question 30

Advantages of Dijkstras

Answer 30

- doesn't need to know the target node before | - good for multiple target nodes

Question 31

Disadvanatges of Dijkstras

Answer 31

- doesn't work for negative edge weights | - slower than A*

Question 32

Advantages of A*

Answer 32

- faster - always find a solution if it exists - can be morphed into other path finding algorithms by changing the heuristic

Question 33

Disadvanatges of A*

Answer 33

- no good if you have many target nodes | - not good if you have no prior knowledge of the network

Question 34

bubble best average worst

Answer 34

O(n), O(n^2), O(n^2)

Question 35

bubble space

Answer 35

O(1)

Question 36

insertion best average worst

Answer 36

O(n), O(n^2), O(n^2)

Question 37

insertion space

Answer 37

O(1)

Question 38

merge best average worst

Answer 38

O(nlogn), O(nlogn), O(nLogn)

Question 39

merge space

Answer 39

O(n)

Question 40

quick best average worst

Answer 40

O(nlogn), O(nlogn), O(n^2)

Question 41

quick space

Answer 41

O(logn)

Question 42

Linear search best average worst

Answer 42

O(1), O(n), O(n)

Question 43

Binary search best average worst

Answer 43

O(1), O(logn), O(logn)