2.3.1 Algorithms Flashcards Preview

A Level Computer Science > 2.3.1 Algorithms > Flashcards

Flashcards in 2.3.1 Algorithms Deck (30)
Loading flashcards...
1

Define a linear search

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

2

What are the key points of a linear search?

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

3

What are the advantages of a linear search?

Easy to implement

Works on ordered or unordered lists

Easy to add items

4

What are the disadvantages of a linear search?

Usually most inefficient on longer lists

5

Define a binary search

An algorithm for finding an item in a sorted list.

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

6

What are the key points of a binary search?

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

7

What are the advantages of a binary search?

Efficient

Suitable for large data sets

8

What are the disadvantages of a binary search?

Only works on ordered lists

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

9

Define a bubble sort

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

It 'bubbles' the smallest/largest number to the ends

10

How does a bubble sort work?

  • 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

11

What are the advantages and disadvantages of a bubble sort?

Advantage: works well on small lists

Disadvantage: slow to work

12

Define an insertion sort

Slots each item into the correct position in a data set

13

How does an insertion sort work?

  • 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

14

What are the advantages and disadvantages of an insertion sort?

Advantage: works well on small lists

Disadvantage: slow to work

15

Define a merge sort

Uses 'divide and conquer' to quickly sort data.

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

16

How does a merge sort work?

  • 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

17

Define a quick sort

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.

18

How does a quick sort work?

  • 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

19

Define the 'Dijkstra's Shortest Path algorithm'

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

20

Define the 'A* algorithm'

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

21

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

Advantage:

Finds the shortest time to a location

Disadvantage:

Every vertex must be investigated

22

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

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

23

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

  • 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

24

How is the A* algorithm carried out?

  • 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

25

What are the 5 main Big O notations?

Constant: O(1)

Logarithmic: O(log n)

Linear: O(n)

Polynomial: O(n2)

Exponential: O(nn)

26

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

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

27

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

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

28

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

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

29

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

  • 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

30

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

  • 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