Unit 12 Algorthiums

Question 1

What two pieces of information allow you to analyse an algorithm?

Answer 1

● Time Complexity
● Space Complexity

Question 2

What is meant by the time complexity of an algorithm?

Answer 2

The time complexity of an algorithm is how much time it requires to solve a particular problem. The time complexity is measured using a notation called big-o notation, which shows the effectiveness of the algorithm. It shows an upper limit for the amount of time taken relative to the number of data elements given as an input. This is good because it allows you to predict the amount of time it takes for an algorithm to finish given the number of data elements.

Question 3

How do you measure of the time complexity?

Answer 3

Big-O notation

Question 4

What does the Big-O notation show?

Answer 4

The effectiveness of an algorithm

Question 5

What is the Big-O notation good for?

Answer 5

It allows you to predict the amount of time taken to solve an algorithm given the number of items stored

Question 6

What does a linear time complexity mean?

Answer 6

The amount of time taken to complete an algorithm is independent from the number of elements inputted. O(n)

Question 7

What does a constant time complexity mean?

Answer 7

The amount of time taken to complete an algorithm is independent to the number of inputted elements. O(1)

Question 8

What does a polynomial time complexity mean?

Answer 8

The amount of time taken to complete an algorithm is proportional to the number of items inputted to the power of n. O(n2)

Question 9

What does an exponential time complexity mean?

Answer 9

The amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items inputted. O(2N)

Question 10

What does a logarithmic time complexity mean?

Answer 10

The time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted. O(Log n)

Question 11

What is a logarithm?

Answer 11

How many times a certain number (base) is multiplied together to reach another number.

Question 12

What is space complexity?

Answer 12

The space complexity of an algorithm is the amount of storage the algorithm takes. Space complexity is commonly expressed using Big O (O(n)) notation. Algorithms store extra data whenever they make a copy, this isn’t ideal. When working with lots of data, it’s not a good idea to make copies. As this will take lots of storage which is expensive.

Question 13

What is an algorithm?

Answer 13

An algorithm is a series of steps that complete a task

Question 14

How do you reduce the space complexity?

Answer 14

Try to complete all of the operations on the same data set

Question 15

How do you reduce the time complexity of an algorithm?

Answer 15

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

Question 16

What is the Big-O notation of a linear search algorithm?

Answer 16

O(n)

Function linearSearch(list, item)
index = -1
i= 0
found = False
while i < length(list) and found = False
if list[i] = item then
index = i
found = True
endif
i=i+ 1
endwhile
return index
endfunction

Question 17

What is the Big-O notation of a binary search algorithm?

Answer 17

O(log(n))

function binarySearch(list, item)
found = False
index = -1
first = 0
last = length(list) - 1
while first <= last and found = False
midpoint = int ( first + last) / 2 )
if list[midpoint] = item then
found = True
index = midpoint
else
if list[midpoint] < item then
first = midpoint + 1
else
last = midpoint - 1
endif endif
endwhile
return index
endfunction

Question 18

What is the Big-O notation of a bubble sort algorithm?

Answer 18

O(n2)

function bubbleSort(list, item)
found = False
i= 0
while found = False and i < length(item)
if list[i] > list[i+1]
temp = list[i]
list[i] = list[i+1]
list[i+1] = temp
endif
i = i +1
endwhile
return list
endfunction

Question 19

Stacks

Answer 19

Stacks are an example of a ​first in, last out ​(FILO) data structure. They are often implemented as an array ​and use a​ single pointer ​which keeps track of the top of the stack (called the top pointer). This points to the element which is​ currently at the top ​of the stack.

The top pointer is initialised at -1; this is because the first element in the stack is in position 0, and having the top initialised at 0 would suggest there is an element in the stack, when in fact the stack is empty.

Algorithms for stacks include adding to the stack, removing from the stack and checking whether the stack is empty/full. These have their own​ special names​, as shown in the table below.

Question 20

Stack Operations

Answer 20

size()
isEmpty()
peek()
push(element)
pop()

Question 21

size()

Answer 21

Size returns the ​number of elements ​on the stack. The pseudocode is as simple as returning the value of the top pointer plus one (remember that the first element is in position 0).

 size()
      return top + 1

Question 22

isEmpty()

Answer 22

To check whether a stack is empty, we need to check whether the top pointer is​ less than 0​. If it is, then the stack is empty, otherwise there is data in the stack

 isEmpty()
      if top < 0:
           return True
      else:
           return False
      endif

Question 23

peek()

Answer 23

To return the item at the top of the stack, ​without removing it​, simply return the item at the position indicated by the top pointer. For these examples, we’ll assume our stack is an array called A.

Don’t forget to check that the stack ​has data in it ​before attempting to return data though, as an empty stack could cause errors. It’s useful to use the ​isEmpty​function here.

 peek()
      if isEmpty():
           return error
      else:
           return A[top]
      endif

Question 24

push(element)

Answer 24

To add an item to a stack, the new item must be​ passed as a parameter​. Firstly, the top pointer is updated accordingly. Then the new element can be inserted at the position of the top pointer.

 push(element)
      top += 1
      A[top] = element

Question 25

pop()

Answer 25

To​ remove an item ​from a stack, the element at the position of the top pointer is recorded before being removed, and then the top pointer ​decremented by one ​before the removed itemisreturned.Aswith​peek(),​it’simportanttocheckthatthestack​isn’tempty​before attempting a pop.

 pop()
      if isEmpty():
           return error
      else:
           toRemove = A[top]
           A[top] = “”
           top -= 1
           return toRemove endif

Question 26

Queue

Answer 26

Queues are a type of​ first in, first out ​(FIFO) data structure. Just like stacks, queues are
often represented as arrays. However, unlike stacks, queues make use of two pointers: front and back​. While front holds the position of the first element, back stores the ​next available space​.

Question 27

Queue Operations

Answer 27

size()
isEmpty()
peek()
enqueue(element)
dequeue()

Question 28

size()

Answer 28

To work out the size of a queue, simply​ subtract the value of front from back​. If front is at 0 and back is at 5, there are 5 elements in the queue.

 size()
      return back - front

Question 29

isEmpty()

Answer 29

isEmpty()
When a queue is empty, front and back​ point to the same position​. To check whether a queue is empty, just check whether the two pointers hold ​the same value​.

 isEmpty()
      if front == back:
 return True else:
 return False endif

Question 30

Peek()

Answer 30

Just as with a stack, peek returns the element at the front of the queue ​without removing it​.

peek()
return A[front]

Question 31

enqueue(element)

Answer 31

To add an element to a queue, the element is placed in the position of the back pointer and then back is ​incremented by one​.

 enqueue(element)
      A[back] = element back += 1

Question 32

dequeue()

Answer 32

Items are removed from a queue from the ​position of the front pointer​. Just as with stacks, it’s important to check that the queue​ isn’t empty ​before trying to dequeue an element.

 dequeue()
      if isEmpty():
           return error
      else:
           toDequeue = A[front]
           A[front] = “”
           front += 1
           return toDequeue

Question 33

Linked Lists

Answer 33

A linked list is composed of ​nodes​, each of which has a pointer to the ​next item ​in the list.
If a node is referred to as N, the next node can be accessed using ​N.next​. The first item in a list is referred to as the ​head ​and the last as the ​tail​.

Searching a list is performed using a linear search, carried out by sequential next operations until the desired element is found.

Question 34

Trees

Answer 34

Trees are formed from ​nodes ​and ​edges​, which ​cannot contain cycles ​and ​aren’t directed​. Trees are useful as a data structure because they can be ​traversed​.

There are two types of traversal to cover: ​depth first ​(post-order) and ​breadth first​. Both of these traversals can be implemented ​recursively ​and differ only in the order in which nodes are visited.

Question 35

Depth first (post-order) traversal

Answer 35

Depth first search goes ​as far down into the tree as possible ​before backtracking. The algorithm uses a ​stack ​and goes to the​ left child node ​of the current node when it can. If there is no left child then the algorithm goes to the​ right child​.

If there are no child nodes, the algorithm ​visits ​the current node, outputting the value of the node before backtracking to the next node on the stack and ​moving right​.

Question 36

Breadth first

Answer 36

Starting from the left, breadth-first visits ​all children ​of the start node. The algorithm then visits all nodes ​directly connected ​to each of those nodes in turn, continuing until every node has been visited. Unlike depth first traversal (which uses a stack), breadth first uses a ​queue​.

Question 37

Bubble Sort

Answer 37

Bubble sort makes ​comparisons and swaps ​between pairs of elements. The largest element in the unsorted part of the input is said to “bubble” to the top of the data with each iteration of the algorithm.

The algorithm starts at the first element in an array and compares it to the second. If they are in the wrong order, the algorithm ​swaps ​the pair. Otherwise, the algorithm moves on. The process is then repeated for every adjacent pair of elements in the array until the end of the array is reached (at which point the largest element is in the last position of the array).

This is referred to as one ​pass ​of the algorithm. For an array with n elements, the algorithm will perform n passes through the data, at which point the input is sorted and can be returned.

Question 38

Bubble Sort Pseudocode

Answer 38

A = A​rray of data
for i = 0 to A.length - 1:
noSwap = True
for j=0 to A .length-(​i+1):​
if A[j] > A[j+1]:
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
noSwap = False
if noSwap:
break
return A

Question 39

Insertion Sort

Answer 39

Another sorting algorithm, insertion sort ​places elements into a sorted sequence​. In the ​i​th iteration of the algorithm, the first ​i​elements of the array are sorted. Be careful though, although ​i​elements are ​sorted​, they are not the ​i​smallest elements ​in the input.

Question 40

Insertion sort Pseudocode

Answer 40

A = A​rray of data
for i = 1 to A.length - 1:
elem = A[i]
j = i -1
while j > 0 and A[j] > elem:
A[j+1] = A[j]
j = j -1 A[j+1] = elem

Question 41

Merge Sort

Answer 41

Merge sort is an example of a class of algorithms known as “​divide and conquer​” for reasons which will soon become clear.

Merge sort is formed from​ two functions​. One called ​MergeSort​and another called Merge​. ​MergeSort​divides its input into two parts and ​recursively ​calls ​MergeSort​on each of those two parts until they are of length 1 at which point ​Merge​is called. ​Merge puts groups of elements back together in a special way, ensuring that the final group produced is sorted.

Question 42

Merge sort Pseudocode

Answer 42

A = A​rray of data
MergeSort(A)
if A.length <= 1:
return A
else:
mid = A.length / 2
left = A[0…mid]
right = A[mid+1…A.length-1]
leftSort = MergeSort(left)
rightSort = MergeSort(right)
return Merge(leftSort, rightSort)

Question 43

Quick Sort

Answer 43

Quick sort works by ​selecting an element​, often the central element (called a ​pivot​), and dividing the input ​around it. Elements smaller than the pivot are placed in a list to the left of the pivot and others are placed in a list to the right.

This process is then repeated ​recursively ​on each new list until all elements in the input are​ old pivots themselves ​or ​form a list of length 1​. Despite the name, quick sort​ isn’t particularly fast​, in fact it’s time complexity is ​O(n2​)​ ​.

Question 44

Searching algorithms

Answer 44

Searching algorithms are used to​ find a specified element ​within a data structure. For example, a searching algorithm could be used to find the name “Alan Turing” in an array of names.

Numerous different searching algorithms exist, each of which is ​suited to a particular data structure ​of​ format of data​. Different searching algorithms are used depending on each individual scenario.

Question 45

Binary Search

Answer 45

The binary search algorithm can only be applied on ​sorted data ​and works by finding the middle element ​in a list of data before deciding ​which side ​of the data the desired element is to be found in. The unwanted half of the data is then ​discarded ​and the process repeated ​until the desired element is ​found ​or until it is known that the desired element doesn’t exist ​in the data.

Pseudocode for binary search is shown below.
A =​ Array of data
x =​ Desired element
low = 0
high = A.length -1
while low <= high:
mid = (low + high) / 2
if A[mid] == x:
return mid
else if A[mid] > x:
high = mid -1
else:
low = mid + 1
endif
endwhile
return “Not found in data”

Question 46

Linear Search

Answer 46

Linear search is the​ most basic ​searching algorithm. You can think of it as going along a bookshelf one by one until you come across the book you’re looking for. Sometimes the algorithm​ gets lucky ​and finds the desired element almost ​immediately​, while in other situations, the algorithm is ​incredibly inefficient​. It’s time complexity is ​O(n)​.
There’s a lot of ​pot luck ​involved with linear search, but it’s incredibly ​easy to implement​. Unlike binary search, linear search doesn’t require the data to be sorted.

A =​ Array of data
x =​ Desired element
i= 0
while i < A.length:
if A[i] == x:
return i
else:
i = i +1
endif
endwhile
return “Not found in data”

Question 47

Dijkstra’s algorithm

Answer 47

Dijkstra’s algorithm finds the ​shortest path between two nodes in a weighted graph​. Remember that graphs are used as an abstraction for a variety of real life scenarios, which means nodes and edges can represent different entities. For example, graphs can be used to model networks, with nodes representing devices and arc costs representing network traffic. In this scenario, Dijkstra’s algorithm can be used to determine the optimal route to use when forwarding packets through a network.

Regardless of the scenario, complexity or size of the graph, Dijkstra’s algorithm can be used to work out the shortest path using a consistent method each time. The algorithm is commonly implemented using a ​priority queue​, with the smallest distances being stored at the front of the list.

Question 48

A* Algorithm

Answer 48

The A* Algorithm is a general path-finding algorithm which is an improvement of Dijkstra’s algorithm and has ​two cost functions​:
1) The first cost function is the actual cost between two nodes. This is the same cost as is measured in Dijkstra’s algorithm.
2) The second cost function is an ​approximate cost from node x to the final node​. This is called a heuristic, and aims to make the shortest path finding process more efficient. The approximate cost might be an estimate of the length between x and the final node, calculated using trigonometry.

When calculating the distance between two nodes using the A* algorithm, the approximate cost is added onto the actual cost. This is used to determine which node is visited next. This differs from Dijkstra’s algorithm as a node with a lower actual cost may be rejected in favour of a node with a lower total cost. This is meant to reduce the total time taken to find the shortest path. The heuristic costs are labelled in red on the diagram.