Unit 12 Algorithms

Question 1

What is an algorithm?

Answer 1

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

Question 2

What are some examples of computational algorithms? (3)

Answer 2

• Binary search
• Insertion Sort
• Bubble Sort

Question 3

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

Answer 3

• Routing problems
• Timetabling aircrafts
• Searching information on the Internet
• Encrypting communications
• Sorting large amounts of data
• Writing a compiler program

Question 4

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

Answer 4

• 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

Question 5

What is a good basic measure of Efficiency?

Answer 5

The number of assignment statements

Question 6

What is a Linear Function?

Answer 6

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

Question 7

What is a Quadratic Function?

Answer 7

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

Question 8

What is a Logarithmic Function?

Answer 8

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

Question 9

What is the Logarithm of a number?

Answer 9

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

Question 10

What is Big-O Notation?

Answer 10

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

Question 11

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

Answer 11

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

Question 12

How does a Divide and Conquer Algorithm work?

Answer 12

It halves the size of the problem at each pass

Question 13

What is a Permutation?

Answer 13

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

Question 14

What are the types of Permutation? (2)

Answer 14

• Repetition allowed
• No repetition allowed

Question 15

What is Big-O notation used for?

Answer 15

Describing the time complexity of different algorithms

Question 16

What happens in a Linear Search?

Answer 16

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

Question 17

What is the worst case scenario of a Linear Search?

Answer 17

Every item is checked

Question 18

What happens in a Binary Search? (4)

Answer 18

• 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

Question 19

What do Binary Trees do?

Answer 19

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

Question 20

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

Answer 20

The list must be sorted

Question 21

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

Answer 21

O(log n)

Question 22

What is the time complexity for a Linear Search?

Answer 22

O(n)

Question 23

When is a Bubble Sort best used?

Answer 23

When there are only a small number of items

Question 24

What happens in a Bubble Sort?

Answer 24

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

Question 25

What happens in an Insertion Sort?

Answer 25

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

Question 26

What is the time complexity of Bubble and Insertion Sort?

Answer 26

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

Question 27

What happens in a Merge Sort? (2)

Answer 27

- 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

Question 28

What is the time complexity for Merge Sort?

Answer 28

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

Question 29

What happens in a Quick Sort?

Answer 29

- 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

Question 30

What is the best time complexity for Quick Sort?

Answer 30

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.

Question 31

What is the worst time complexity for Quick Sort?

Answer 31

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)

Question 32

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

Answer 32

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

Question 33

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

Answer 33

- Depth-first - Breadth-first

Question 34

What happens in Depth-first traversal?

Answer 34

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

Question 35

What happens in Breadth-first traversal?

Answer 35

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

Question 36

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

Answer 36

- 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

Question 37

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

Answer 37

- 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

Question 38

What is Dijkstra's Shortest Path Algorithm?

Answer 38

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

Question 39

When is a problem defined as computable?

Answer 39

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

Question 40

What are limits of computation? (2)

Answer 40

- Algorithmic complexity - Hardware

Question 41

What is the Travelling Salesman Problem?

Answer 41

“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?”

Question 42

Why does the Brute Force Method not work on the TSP

Answer 42

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

Question 43

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

Answer 43

No, it is intractable

Question 44

What is a Tractable problem?

Answer 44

A problem that has a polynomial-time solution

Question 45

What is a Heuristic solution?

Answer 45

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

Question 46

What does the A* Algorithm do?

Answer 46

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

Question 47

How does Depth-First Traversal work?

Answer 47

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

Question 48

How does Breadth-First Traversal Work? (3)

Answer 48

-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