Algorithms Flashcards Preview

A-Level Computer Science OCR > Algorithms > Flashcards

Flashcards in Algorithms Deck (43)
Loading flashcards...
1
Q

binary search precondition

A

the list needs to be sorted

2
Q

Insertion sort

A

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.

3
Q

linear search

A

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

4
Q

Binary search

A

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

5
Q

Four sorting algorithms

A

Bubble, Insertion, Quick, Merge

6
Q

Insertion sort words

A

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

7
Q

Merge sort

A

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.

8
Q

Why does merge split down into unit lists

A

because a list of length one is sorted

9
Q

Merge algorithm

A
  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.
10
Q

Quick sort algorithm

A

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

11
Q

Quick sort

A

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.

12
Q

Where can the pivot be applied

A

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

13
Q

advantages bubble

A
  • simple
14
Q

disadvantages bubble

A
  • long time to run
15
Q

advantages insertion

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

disadvantages insertion

A
  • poor performance with larger lists

- not as quick as merge/quick sort

17
Q

disadvantages quick

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

advantages quick

A
  • very efficient

- no additional storage required/ less stack memory

19
Q

advantages merge

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

disadvantages merge

A
  • 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
21
Q

advantages Linear search

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

disadvantages linear search

A
  • May be too slow over large lists
23
Q

advantages binary search

A
  • Works well with larger lists

- Quicker

24
Q

disadvantages binary search

A
  • Small lists simpler to use linear search

- Cannot deal with unordered lists

25
Q

Shortest path algorithms

A

Dijkstras and A*

26
Q

Dijkstras table columns

A

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

27
Q

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

A

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

28
Q

A*

A

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

29
Q

A* table

A

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

30
Q

Advantages of Dijkstras

A
  • doesn’t need to know the target node before

- good for multiple target nodes

31
Q

Disadvanatges of Dijkstras

A
  • doesn’t work for negative edge weights

- slower than A*

32
Q

Advantages of A*

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

Disadvanatges of A*

A
  • no good if you have many target nodes

- not good if you have no prior knowledge of the network

34
Q

bubble best average worst

A

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

35
Q

bubble space

A

O(1)

36
Q

insertion best average worst

A

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

37
Q

insertion space

A

O(1)

38
Q

merge best average worst

A

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

39
Q

merge space

A

O(n)

40
Q

quick best average worst

A

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

41
Q

quick space

A

O(logn)

42
Q

Linear search best average worst

A

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

43
Q

Binary search best average worst

A

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