2.3 Algorithms

• Using Big-O notation state the best case complexity of insertion sort.

  O(n)
• Explain what your answer to part (b)(i) means.

  • The best case is for a sorted list (O(n))
  • As the number of elements increases the number of steps increases in a linear fashion

  
• A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

  Explain why a linked list is being used for the ordering system


  • Orders can be processed in the order they are in the queue
  • Orders can be inserted at any place in the list e.g. high priority item inserted earlier in the list
  • Orders can be deleted from any position in the list once they are complete
  • List is dynamic so it allows orders to be added / deleted
• A user needs to be able to search for, and find, a specific order number.

  State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm

  • linear
  • Items do not have to be in a specific order
  • Binary needs items in order
• Describe the steps that the program would have to take in order to encrypt the characters stored in the stack, and save them in a single variable

  • Pop element from stack
  • Convert to ASCII value
  • Subtract 10 from ASCII value
  • Convert back to character
  • Append/concatenate with variable

  
• Identify the data structure shown in Fig. 4.1.

  Tree // Graph (undirected)

  
• Explain the difference between a depth-first (post-order) and breadth-first traversal

  • Depth-first goes to left child node when it can If there is no left child it goes to the right child
  • when there are no child nodes the algorithm ‘visits’ it’ and backtracks to the parent node.
  • Breadth-first visits all nodes connected directly to start node
  • Then visits all nodes directly connected to each of those nodes (and then all nodes directly connected to those nodes and so on…)
  • Depth-first uses a stack
  • Breadth-first uses a queue
• State the complexity of searching the pets in Big-O notation.

  O(n)

  
• Define the term ‘queue’


  • A data structure
  • FIFO (first in first out)
• Describe the stages of a binary search on an array of size n.

  • Repeat
  • Calculating an array midpoint by adding the array lower bound to the array upper bound, dividing by 2 and rounding
  • Compare array midpoint with value to search for if equal set found flag to true
  • if array midpoint < value to search for, change lowerbound to equal midpoint + 1
  • if array midpoint > value to search for, change upperbound to equal midpoint – 1
  • Until lowerbound is greater than or equal to upperbound  Return/output found flag
• Compare the performance of Dijkstra’s algorithm and the A* search algorithm, making reference to heuristics, to find the shortest path to the problem


  • Heuristic helps produce a solution in a faster time
  • A* uses estimated distance from final node
  • Dijkstra uses a weight/distance
  • A* chooses which path to take next based on lowest current distance travelled
  • A* will differ from Dijkstra, e.g. taking the shorter route A-B-E-I before exploring nodes from D and E
  • A* doesn’t need to find all possible solutions (saves time)
  • Small-scale problem
  • Quick to find a solution using either method
• The algorithm needs to be used in different scenarios, with a range of different trees.

  Identify two preconditions needed of a tree for this algorithm to work.

  • It’s a binary tree
  • It’s ordered / sorted
• Explain why an insertion sort might use less memory than a merge sort

  • Merge sort might create a new array each time it splits and merges often implemented recursively which places additional data on the stack
  • Insertion sort does not use any additional arrays
  • Insertion sort is an in-place algorithm.
• The data is to be stored in a data structure. The programmer stores the data in a queue.

  Explain why a queue is used instead of a stack


  • Queue outputs data in a First In First Out fashion
  • It will retrieve the temperature values in the order they were recorded
• Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation

  • Compares each pair of data (0 and 0.5)
  • If they are in the correct order it moves to the next pair (0.5 and 0 )
  • If they are in the wrong order it swaps them (0.5 and 0) becomes 0 and 0.5
  • Continues to the end of the array e.g. Pass 1 complete
  • If there has been a swap it checks again e.g. Pass 2 complete
  • If there have been no swaps it is sorted

  
• Describe what Best time O(n) means

  Linear

  • Best time grows at the same rate as the number of elements
  • This is the case when the data is already in order
• Describe what Average and worst time O(n^2) means

  Polynomial / Quadratic

  • Worst and average time is proportional to the square (polynomial) of the number of elements
  • Worst case is when the data is initially in the reverse order
• Describe what Worst Space O(1) means

  Constant

  • Will always take the same amount of memory (in addition to the list itself).
• Hosta needs removing from the linked list.

  Explain how a data item is removed from a linked list. Use the removal of Hosta in your answer.


  • Traverse the list to the item immediately prior to the item to be removed which is DataItem 1 - Daisy
  • Find the value of the NextPointer of the item to be removed which is the NextPointer of DataItem 2 - Hosta, value 7
  • Set the nextPointer of the item prior to the item to be removed to the NextPointer value of the DataItem to be removed
  • update the NextPointer of DataItem 1 - Daisy from 2 to 7 (Lavender)

  
• State the purpose of the pointers queueHead and queueTail.

  queueHead:

  • Point to the first element in the queue
  • next element to remove
  • queueTail:
  • Point to the last element in the queue
• Describe how a bubble sort will sort an array of 10 elements.

  Compare each pair of adjacent elements

  • If they are not in the correct order then swap the elements
  • If they are in the correct order then do no swap elements
  • When you read the end of the array return to the start
  • Repeat n elements time
  • Set a flag to be false whenever a swap is made
  • Repeat the loop if the flag is not false
• State whether the procedure insertionSort sorts the data into ascending or descending order and explain your choice.

  Descending order

  • Line 07 (dataArray[tempos] <temp has the comparison hat checks if current position is less than item to insert and breaks out of loop when current position is less than or equal to item to insert

  
• State the name of the standard algorithm thisFunction() performs

  Binary search

  
• Give two similarities and two differences between a tree and a graph data structure.


  Similarities

  • Both consists of nodes
  • Both are connected by edges/links
  • Both are non-linear data structures
  • Both are dynamic data structures

  Differences

  • Tree is 1-directional whereas a graph is 2-directional
  • Tree has a root node whereas a graph does not have a (clear) root node
  • Tree will not have cycles whereas graphs can contain cycles
  • Tree will not be weighted whereas edges in a graph can be weighte
• State why the tree shown in Fig. 1 is not an example of a binary search tree.


  One node (node A) has more than 2 connections

  • Nodes aren’t ordered (e.g. F is C’s left child)

  
• State what type of pointers are used to store nodes I, F, J and H so they do not point to any other nodes.

  • Null pointers

  
• Show how a breadth-first traversal would traverse the tree shown in Fig. 1.


  Take A as starting node

  •Visit B, C and E

  • Visit D, F, G and H

  • Visit I and J

  
• The move represented by node ‘E’ needs to be deleted. Describe the steps an algorithm will follow to delete node ‘E’ from the tree.

  Search the tree to find the location of Node E

  • Replace the content of node E with blank/null/equivalent
  • Make node A point to the node H
  • Add node E to the empty node list
• The move represented by the node ‘K’ needs to be added. Node ‘K’ needs to be joined to node ‘G.’ Describe the steps the algorithm will follow to add node ‘K’ to the right of node ‘G’


  Search the tree to find the location of node G

  • Create a new node with value K
  • Add a pointer from node G to the new node
  • Make node K point to null/equivalent

  
• Define the term heuristic in relation to the A* algorithm


  A rule of thumb / estimate / guess

  • That estimates the distance / cost from each node to the destination node
  • To speed up the process of finding a solution by identify which paths to follow first
• Identify one situation where a linear search is more appropriate than a binary search


  Data is not sorted

  • Item you are looking for is the first item in the list
  • Small number of items
• A one dimensional array holds data that needs to be sorted. Describe how a quicksort would sort data into ascending order


  Choose a pivot // identify start and end pointers

  • Compare each element to the pivot
  • compare start and end pointers
  • Put items < pivot in the left sublist
  • Put items > pivot in the right sublist
  • Choose a pivot in each sublist
  • If start pointer is larger than end pointer
  • then swap data items around
  • And repeat the process until each item becomes a pivot
• Explain why a quicksort is known as a divide and conquer algorithm.

  decomposing data sets into smaller subsets

  • and then sorting each split subset
  • until each subset is sorted
  • and then combining the subsets to provide a solution
• Describe the steps the procedure enqueue() will follow when adding new items to the queue

  Check if the queue is full

  • if the firstElement pointer (+1) = lastElement
  • length variable == queue’s capacity
  • if it is return False
  • Adds element at lastElement (+1) position
  • Adds element at startposition+length
  • increments lastElement pointer
  • If lastElement is greater than last Index
  • pointer becomes pointer MOD array.size • …reset to 0
• Describe how an array can be used to implement a queue data structure

  Queue has head pointer and tail pointer

  • When an item is enqueued the tail pointer increments
  • When an item is dequeued the head pointer increments
• State the purpose of pointerValue

  Point to the next free space in the array

  • Points to the top of the stack

  
• Give a similarity and difference between the performance of Dijkstra’s algorithm and the performance of A* algorithm.

  Similarities:

  • Both always find the shortest route
  • Both are pathfinding algorithms

  Differences:

  • A* is (usually) more efficient // Dijkstra's is (usually) slower
  • A* uses heuristics to find a solution faster // Dijkstra’s does not use heuristics
• State one way a directed graph is different to an undirected graph

  In directed arcs/edges may only go in 1 direction

  • in undirected arcs/edges can go in both directions
• State one way a graph data structure is different to a tree data structure.

  More than one path is allowed in a graph

  • Graphs do not have a root node
  • Graphs can be weighted
  • Graphs can have loops/cycles
• Compare the use of a breadth-first traversal and a depth-first (post-order) traversal on the binary search tree


  Breadth first takes first value then visits all nodes connected to it. It then takes all nodes connected to those nodes.

  • Depth first goes to the left node, this becomes a new tree. It continues going to the left until a leaf.
  • Breadth is more efficient when the data searched for is closer to the root.
  • Depth is more efficient when data to be search for is further down.
  • Breadth in general is better time complexity