Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

OCR Computing A Level LTS (Set 1) > Unit 12 Algorithms > Flashcards

Unit 12 Algorithms Flashcards

1
Q

What is an algorithm?

A

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are some examples of computational algorithms? (3)

A
  • Binary search
  • Insertion Sort
  • Bubble Sort
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What kind of problems are solved by Algorithms? (6)

A
  • Routing problems
  • Timetabling aircrafts
  • Searching information on the Internet
  • Encrypting communications
  • Sorting large amounts of data
  • Writing a compiler program
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the properties of a good algorithm? (5)

A
  • Has clear and well stated steps
  • Should allow for invalid inputs
  • Must terminate at some point
  • Should be executed efficiently and in as few steps as possible
  • Must be easy to understand and modify by other people
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a good basic measure of Efficiency?

A

The number of assignment statements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a Linear Function?

A

A function that takes the form of f(n) = an + b where a and b are constants

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a Quadratic Function?

A

A function that takes the form of f(n) = an^2 +bn + c where a, b and c are constants

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Logarithmic Function?

A

A function that takes the form of f(n) = alog2n (that’s a little low 2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the Logarithm of a number?

A

The power to which the base must be raised to make it equal to the number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is Big-O Notation?

A

A measure of the time complexity of an algorithm. It is a useful approximation of the time taken to execute an algorithm for a given number of items in a data set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How does an algorithm of time complexity O(n) increase?

A

Linearly
e.g. 10,000 items will take approximately twice as long as 5,000 items to process

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How does a Divide and Conquer Algorithm work?

A

It halves the size of the problem at each pass

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a Permutation?

A

A permutation of n items is the number of ways the n items can be arranged

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the types of Permutation? (2)

A
  • Repetition allowed
  • No repetition allowed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is Big-O notation used for?

A

Describing the time complexity of different algorithms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What happens in a Linear Search?

A

Each item is checked one after another until the desired item is found

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the worst case scenario of a Linear Search?

A

Every item is checked

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What happens in a Binary Search? (4)

A
  • Middle item is examined
  • If it is the desired item, the item is found
  • If not, depending on whether the current item is higher or lower than the desired item, half the list is eliminated
  • This is repeated until the item is found or proved to not be in the list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What do Binary Trees do?

A

Hold items in a way that can be searched quickly and easily

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What must be true for a Binary Search to take place?

A

The list must be sorted

21
Q

What is the time complexity for a Binary Search and Binary Tree?

A

O(log n)

22
Q

What is the time complexity for a Linear Search?

A

O(n)

23
Q

When is a Bubble Sort best used?

A

When there are only a small number of items

24
Q

What happens in a Bubble Sort?

A

n-1 passes are made through the array, with each adjacent item being compared with the adjacent item and swapped if necessary

25
Q

What happens in an Insertion Sort?

A

The first item in the list is examined and moved into a sorted list. This is repeated till all items are in the sorted list

26
Q

What is the time complexity of Bubble and Insertion Sort?

A

They both have the same time complexity O(n^2) but the insertion sort is generally faster, although of the same order e.g. the bubble sort may take twice as long to sort 10,000 items

27
Q

What happens in a Merge Sort? (2)

A
  • The unsorted list is divided into n sublists, each containing one element
  • Sublists are repeatedly merged to produce new sorted sublists until there is only one sublist remaining. This is the sorted list
28
Q

What is the time complexity for Merge Sort?

A

O(n log2n)
(that’s a little low 2)

29
Q

What happens in a Quick Sort?

A
  • The algorithm finds a split point, which divided the list into two sublists. One containing items higher than the value at the split point and to other containing items lower
  • The pivot value is typically the first item in the list
30
Q

What is the best time complexity for Quick Sort?

A

For a list of length n, if the split point always occurs in the middle of the list, there will be log n divisions so the best time complexity would be n log n.

31
Q

What is the worst time complexity for Quick Sort?

A

If the split point is very skewed to the left or right, the division will be very uneven
It becomes a case of sorting 2 sublists of 0 items and n-1 items …
…then sorting 0 items and n-2 items, and so on
The result is O(n2)

32
Q

What is a good way of quickly choosing a Pivot Value?

A

Look at the first, middle and last element of the list, and choose the one in the middle of the three

33
Q

What are the ways of traversing a graph? (2)

A
  • Depth-first
  • Breadth-first
34
Q

What happens in Depth-first traversal?

A

You go as far as you can down a path before backtracking and going down the next path

35
Q

What happens in Breadth-first traversal?

A

You explore all the neighbours of the current vertex, then the neighbours of each of those vertices and so on

36
Q

What are applications for Depth-first traversal? (3)

A
  • Job-scheduling, where some jobs have to be completed before others can begin
  • Finding a path between two vertices
  • Solving puzzles such as navigating a maze
37
Q

What are applications for Breadth-first traversal? (3)

A
  • Finding the shortest path between two points
  • A Web crawler uses a breadth-first search to analyse sites that you can reach by following links randomly
  • Facebook uses a breadth-first search to find all the friends of a given individual
38
Q

What is Dijkstra’s Shortest Path Algorithm?

A

An algorithm that is designed to find the shortest path between a start node and every other node in a weighted graph

39
Q

When is a problem defined as computable?

A

When there is an algorithm that can solve every instance of it in a finite number of steps

40
Q

What are limits of computation? (2)

A
  • Algorithmic complexity
  • Hardware
41
Q

What is the Travelling Salesman Problem?

A

“Given a list of towns and the distances between each pair of towns, what is the shortest possible route that the salesman can use to visit each town exactly once and return to the starting point?”

42
Q

Why does the Brute Force Method not work on the TSP

A

Using this method all possible routes are tested. This means it has a complexity of O(n!) which quickly becomes too big to solve within a reasonable time

43
Q

Is using the Brute Force Method an example of a Tractable problem?

A

No, it is intractable

44
Q

What is a Tractable problem?

A

A problem that has a polynomial-time solution

45
Q

What is a Heuristic solution?

A

An approach that tries to find a solution that may not be perfect but which is adequate for its purpose

46
Q

What does the A* Algorithm do?

A

It focusses only on reaching the goal node, unlike Dijkstra’s algorithm which finds the lowest cost or shortest path to every node

47
Q

How does Depth-First Traversal work?

A

The algorithm uses a stack to keep track of the last node visited, and a list to hold the names of nodes that have been visited

48
Q

How does Breadth-First Traversal Work? (3)

A

-With a breadth first traversal, all the nodes adjacent to A are visited before moving to B
-The process is repeated for each node at this ‘level’, before moving to the next level
-Instead of a stack, a queue is used to keep track of nodes that we still have to visit

OCR Computing A Level LTS (Set 1) (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions