2.3.1

Question 1

Algorithms

Answer 1

• A set of instructions used to solve a set problem.
• Inputs must be clearly defined.
• Must always produce a valid output.
• Must be able to handle invalid inputs.
• Must always reach a stopping condition.
• Must be well-documented for reference.
• Must be well-commented.

Question 2

Designing Algorithms

Answer 2

• The priority for an algorithm is to achieve the given task.
• The second priority is to reduce time and space complexity.
• There may be a conflict between space and time complexity and the requirements and situation for an algorithm will dictate which is more important.
• To reduce space complexity, make
  as many changes on the original data
  as possible. Do not create copies.
• To reduce time complexity, reduce
  the number of loops.

Question 3

Space Complexity

Answer 3

• The amount of storage space the algorithm takes up.
• Does not have a defined notation.
• Copying data increases the storage used.
• Storage space is expensive so this should be avoided.

Question 4

Time Complexity

Answer 4

• How much time an algorithm needs to solve a problem.
• Measured using big-o notation.
• Shows the amount of time taken relative to the number of inputs.
• Allows the required time to be predicted.

Question 5

0(1) - Consistent time complexity

Answer 5

The amount of time is not affected by the number of inputs.

Question 6

0(n) - Linear time complexity

Answer 6

The amount of time is directly proportional to the number of inputs.

Question 7

0(nn) - Polynomial time complexity

Answer 7

The amount of time is directly proportional to the number of inputs to the power of n.

Question 8

0(2n) - Exponential time complexity

Answer 8

The amount of time will double with every additional input.

Question 9

0(log n) - Logarithmic time complexity

Answer 9

The amount of time will increase at a smaller rate as the number of inputs increases.

Question 10

Stacks

Answer 10

• FILO (First In Last Out)
• Often an array.
• Uses a single pointer (the top pointer) to track the top of the stack.
• The top pointer is initialised at -1, with the first element being 0, the second 1 and so on.

Question 11

Stack Functions

Answer 11

• Check size size()
• Check if empty isEmpty()
• Return top element (but don’t remove) peek()
• Add to the stack push(element)
• Remove top element from the stack and return it pop()

Question 12

Queues

Answer 12

• FIFO (First in first out)
• Often an array.
• The front pointer marks the position of the first element.
• The back pointer marks the position of the next available space.

Question 13

Queue Functions

Answer 13

• Check size size()
• Check if empty isEmpty()
• Return top element (but don’t remove) peek()
• Add to the queue enqueue(element)
• Remove element at the front of the queue and return it dequeue()

Question 14

Trees

Answer 14

• Consists of nodes and edges.
• Cannot contain cycles.
• Edges are not directed.
• Can be traversed using depth first or breadth first.
• Both methods can be implemented recursively.

Question 15

Depth First (Post Order) Traversal

Answer 15

• Moves as far as possible through the tree before backtracking.
• Uses a stack.
• Moves to the left child node wherever possible.
• Will use the right child node if no left child node exists.
• If there are no child nodes, the current node is used.
• the algorithm then backtracks to the
  next node moving right.

Question 16

Breadth First

Answer 16

• Starts from the left.
• Visits all children of the starting node.
• Then visits all nodes directly connected to each of these nodes in turn.
• Continues until all nodes have been visited.

Question 17

Linked Lists

Answer 17

• Contains several nodes.
• Each node has a pointer to the next item in the list.
• For node N, N.next will access the next item.
• The first node is the head.
• The last node is the tail.
• Searched using a linear search.

Question 18

Bubble Sort

Answer 18

• Compares elements and swaps as needed.
• Compares element 1 to element 2.
• If they are in the wrong order, they are swapped.
• This process is repeated with 2 and 3, 3
  and 4, and so on until the end of the list is
  reached.
• This process must be repeated as many
  times as there are elements in the array.
• Each repeat is referred to as a “pass”.
• Can be modified to improve efficiency by
  using a flag to indicate if a swap has
  occurred during the pass.
• If no swaps are made during a pass the list must be in the correct order and so the
  algorithm stops.
• A slow algorithm.
• Time complexity of 0(n2)

Question 19

Insertion Sort

Answer 19

• Places elements into a sorted list.
• Starts at element 2 and compares it with the element directly to its left.
• When compared, elements are inserted into the correct position in the list.
• This repeats until the last element is inserted into the correct position.
• In the 1st iteration 1 element is sorted, in the 2nd iteration 2 are sorted etc.
• Time complexity of 0(n2)

Question 20

Merge Sort

Answer 20

• A divide and conquer algorithm.
• Formed of a Merge and MergeSort function.
• MergeSort divides the input into two parts.
• It then recursively calls MergeSort on each part until their length is 1.
• Merge is called.
• Merge puts the groups of elements back together in a sorted order.
• You will not be asked about the detailed implementation of this algorithm but do need to know how it works.
• It is more efficient than bubble and merge sort.
• It has a worst case time of O(n log n)

Question 21

Quick Sort

Answer 21

• Selects an element and divides the input
  around it.
• Often selects the central element, which
  is known as the pivot.
• Elements smaller than the pivot are listed to its left.
• Larger elements are listed to its right.
• The process is repeated recursively.
• Slow.
• Time complexity of O(n2)

Question 22

A* Algorithm

Answer 22

• Provides a faster solution than Dijkstra’s Algorithm to find the shortest path between two nodes.
• Uses a heuristic element to decide which node to consider when choosing a path.
• Unlike Dijkstra’s Algorithm, A* only looks for the shortest path between two nodes, instead of the shortest path from the start node to all other nodes.

Question 23

Dijkstra’s Algorithm

Answer 23

• Finds the shortest path between two points.
• The problem is depicted as a weighted graph.
• Nodes represent the items in the scenario such as places.
• Edges connect the nodes together.
• Each edge has a cost.
• The algorithm will calculate the best way, known as the least cost path, between two nodes.

Question 24

Linear Search

Answer 24

• Most basic search algorithm.
• Works through the elements one at a time until the requested element is found.
• Does not need data to be
  sorted.
• Easy to implement.
• Not very efficient.
• Time Complexity is 0(n)

Question 25

Binary Search

Answer 25

- Only works with sorted data. - Finds the middle element, then decides on which side of the data the requested element is. - The unneeded half is discarded and the process repeats until either the requested element is found or it is determined that the requested element does not exist. - A very efficient algorithm. - Time Complexity is 0(log n)

Question 26

Logarithms

Answer 26

- The inverse of an exponential. - An operation which determines how many times a certain number is multiplied by itself to reach another number. - x y = log(x) - 1 (20 ) 0 - 8 (23 ) 3 - 1024 (210) 10