Algorithms

Question 1

ideal algorithm

Answer 1

will run quickly and take up as little space(memory) as possible.

Question 2

Time complexity

Answer 2

How much time they need to solve a given problem

Question 3

Space complexity

Answer 3

The amount of resources e.g. memory they require

Question 4

Permutation

Answer 4

number of ways we can arrange a set of data - factorial e.g. 4! = 4x3x2x1

Question 5

Constant

Answer 5

y = 3

Question 6

Linear

Answer 6

y = 3x

Question 7

Logarithmic (Big O + graph)

Answer 7

y = log(x)

O(logn)

Question 8

Polynomial

Answer 8

y = x^2

Question 9

Exponential graph

Answer 9

y = x^3

Question 10

How to write Big O

Answer 10

Notation always assumes the worst case scenario,
1. remove all terms except the one with the largest factor
2. Remove any constants
e.g. 3n is expressed as O(n), this is a linear complexity that grows by ‘n’ number of times

Question 11

Constant complexity

Answer 11

O(1)

Always executes in the same time regardless of the size of the data set - most efficient. Time is independent of input

e.g. Determining if a number is odd or even

Question 12

Logarithmic complexity

Answer 12

O(log n)

Halves the data in each pass. Opposite to exponential and efficient with large data sets - efficient

e.g. Binary search

Linear Logarithmic -
Merge sort = O(n log n)

Question 13

Linear complexity

Answer 13

O(n)

Performance is proportional to the size of the data set and declines as the data set grows. - medium efficiency

In the worst case scenario it must go through each item once

e.g. Linear search

Question 14

Polynomial complexity

Answer 14

O(n^2)

Performance is proportional to the square of the size of the data set. - inefficient

A loop inside a loop

e.g. Bubble sort

Question 15

Exponential complexity

Answer 15

O(2^n)

Doubles with each addition to the data set in each pass, opposite to logarithmic - very inefficient

Intractable

e.g. recursively calculating Fibonacci numbers

Question 16

Constant Time

Answer 16

Time remains constant even when the number of output increases

Question 17

Logarithmic Time

Answer 17

Time will grow as the size of the input increases

Question 18

Linear Time

Answer 18

Time will be linear to the size of the input

Question 19

Polynomial Time

Answer 19

Time will grow proportionally to the square of the size of the data set

Question 20

Exponential Time

Answer 20

Time will be as the power of the number of inputs, grows very quick

Question 21

Factorial Time O(n!)

Answer 21

Time will grow even quicker as data is input, very inefficient

Question 22

Tractable problems

Answer 22

efficient, have a polynomial or less time solution e.g. O(1). O(n), O(log n), O(n^2)

Question 23

Intractable problems

Answer 23

inefficient, any problems that can be theoretically solved but take longer than polynomial time e.g. O(n!), O(2^n)

Question 24

Heuristic algorithms

Answer 24

used to provide approximate but not exact solutions.

Question 25

Unsolvable problems

Answer 25

can never be solved algorithmically, an example is demonstrated by the Halting problem

Question 26

Graph Traversal

Answer 26

Is the process of visiting each vertex in a graph. You can use both depth-first and breadth first

Question 27

Depth First Graph Traversal

Answer 27

a branch is fully explored before backtracking. Uses a stack

Question 28

Breadth First Graph Traversal

Answer 28

a layer is fully explored before venturing on to the next node. Uses a queue

Question 29

Pre-Order Tree Traversal

Answer 29

Drawing a dot on the left of the nodes, used for prefix notation and copying a tree

Question 30

Post-Order Tree Traversal

Answer 30

Drawing a dot on the right of the nodes, used for reverse polish notation

Question 31

In Order Tree Traversal

Answer 31

Drawing a dot underneath the nodes and follow around the nodes – Used for binary tree search and outputting values in ascending order

Question 32

How to represent a tree data structure?

Answer 32

1. An array that contains values at the nodes 2. An array that points to the location of the left child of the node in the values array 3. An array that points to the location of the right child of the node in the values array

Question 33

Reverse Polish Notation

Answer 33

Humans prefer in-fix order notation, this is where operand is either side of the opcode. However RPN creates a postfix equivalent e.g. infix 3 + 5 Postfix/RPN 35+ Both give the answer 8

Question 34

Evaluate the postfix equation 963/+ (Use a stack)

Answer 34

963/+ 63/= 6/3 = 2 92+ = 11 Operand is pushed onto the stack, whilst opcode causes two items to be popped off the stack with the result of the operation pushed back onto the stack.

Question 35

RPN uses/benefits

Answer 35

RPN can be executed on a stack, as a result, RPN is ideal for interpreters which are based on a stack e.g. Bytecode and PostScript RPN is non ambiguous and therefore easier for computers to read

Question 36

Linear Search Operations?

Answer 36

1. Compare every search item against every item in the list one-by-one. 2. Starts at the beginning and keeps going until the search item is found 3. Returns the position of where it is found 4. If the item is not in the list, it will return a suitable message indicating it is not in the list, should not error

Question 37

Big O for time complexity for Linear Search?

Answer 37

Big O = O(N) Linear search is slow when compared with other search algorithms

Question 38

What can Linear Search be conducted on?

Answer 38

any unordered list

Question 39

How can you determine the maxiumum number of searches a binary list performs?

Answer 39

Divide by 2 until you reach 1 or lower, the number of times divded is the max number of searches# (or can use log)

Question 40

What can Binary Search be conducted on?

Answer 40

any ordered list

Question 41

Binary Search Operations?

Answer 41

1. works by looking at the midpoint of the list and determining if the target is higher or lower than the midpoint 2. If when calculating the midpoint it is decimal, the decimal is removed e.g. 2.6 → 2 3. The list is then halved

Question 42

Big O time complexity for Binary Search?

Answer 42

O(logN)

Question 43

Linear Search Advantages and Disadvantages

Answer 43

Advantages; -Simple and easy to implement -No sorting required -Good for short lists Disadvantages; -Slow because it searches through the whole list -Inefficient for long lists

Question 44

Binary Search Advantages and Disadvantages?

Answer 44

Advantages; -Much quicker, halving the search zone Disadvantages; -Items of the list need to be placed in order

Question 45

What kind of algorithm is bubble sort?

Answer 45

Sorting

Question 46

What is the purpose of a Bubble Sort?

Answer 46

The purpose of bubble sort is to order an unordered list, this can be alphabetically or by number.

Question 47

Bubble Sort: Order of Operations

Answer 47

1. Bubble sort steps through a list and compares pairs of adjacent numbers 2. The numbers are swapped if they are in the wrong order. e.g. ascending or descending. 3. The algorithm repeatedly passes through the list until no more swaps are needed 4. Going through the list once is considered 1 pass

Question 48

Bubble sort advantages and disadvantages

Answer 48

Advantages : Very simple to code and robust Disadvantages : Slow, inefficient, especially for long lists

Question 49

What is the maximum number of comparisons a bubble sort can make?

Answer 49

for n items n(n−1)/2

Question 50

What is a merge sort?

Answer 50

Merge sort is a recursive function that calls itself. It is a divide and conquer algorithm

Question 51

Merge Sort: Order of Operations

Answer 51

1. Divides unsorted lists into sublists, until there is one item in each list 2. it then combines pairs of sublists into ordered lists, 3. Continues until only one ordered list remains

Question 52

Merge Sort vs Bubble Sort

Answer 52

Merge sort; - Much faster than bubble sort especially when the number of elements is large O(n log n) - More Complex to code and understand Bubble sort; - Much slower than merge sort especially when the number of elements is large O(n^2) - Easy to code and understand

Question 53

what is Dijkstra

Answer 53

Dijkstra’s shortest path optimisation algorithm finds the shortest path between nodes/vertices in a graph

Question 54

Dijkstra: Order of operations

Answer 54

1. Selects the unvisited node with the shortest path 2. Calculates the distance to each unvisited neighbour 3. Updates the distance of each unvisited neighbour if smaller 4. Once all neighbours have been visited mark node as visited

Question 55

Uses for Dijkstra's algorithm?

Answer 55

Applications of DA is heavily used in computer systems that need to calculate shortest paths: - satellite navigation systems to display shortest or fastest route - Routers in networks to find shortest path when routing packets within networks