Paper 2s

• Depth first


  1. Starts at the root (Lily)

  2. Goes all the way down one branch to the bottom (Begonia)

  3. Stores which nodes it has visited / pushes nodes visited onto a stack

  4. When it cannot go any further, it then backtracks/returns to the previous node

  5. And continues to backtrack until a node is reached with unvisited children, and checks down that branch
• Linked List


  1. Correct NextPointer values

  2. Suitable end/null pointer

  3. Data
• Inserting Lavender


  1. Lavender added in position 7

  2. Hosta points to 7

  3. Lavender points to 3
• Removing an item


  1. Traverse the list to the item immediately prior to the item to be removed

  2. Find the value of the NextPointer of the item to be removed

  3. Set the nextPointer of the item prior to the item to be removed to the NextPointer value of the DataItem to be removed
• Traversing a Linked List

  1. Start at the firstElement in the list

  2. Correctly looping until null pointer found / end of list

  3. Outputting the data element

  4. Accessing the pointer to the next element
• if


  • Branching decides which code is run / only runs code once
• Iteration


  • Repeatedly runs the same code in the same sequence
• By Value


  • The original values do not need to be modified
  • byRef would not work / would cause the routine to crash
• MOD


  • Gives the remainder after division
  • E.g. 10 MOD 3 = 1
• GCD


  1. Num2 != 0 therefore return GCD(20,10)

  2. Num2 != 0 therefore return GCD(10,0)

  3. Final return value = 10
• Iteration


  • The program can/might run faster
  • Cannot run out of stack space/memory
  • Easier to trace/follow
• Recursion


  • Iteration can lead to lengthier code
  • Iteration can lead to code that looks more complex / is harder to understand
  • Some problems are more elegantly coded with a recursive solution
• Iterative GCD(The greatest common divisor)


  1. function newGCD(num1, num2)

  2. temp = 0

  3. while (num2 != 0)

  4. temp = num2

  5. num2 = num1 MOD num2

  6. num1 = temp

  7. endwhile

  8. return num1

  9. endfunction
• Splitting a problem into sub-problems


  • She can split the problem down into sub problems
  • It will creates a more manageable problem / simpler to understand / maintain
  • Can tackle each sub problem independently
• Pipelining


  • The result from one process / procedure feeds into the next
  • E.g. the result of detecting a character touching an enemy feeds into reducing the number of lives
• IDEs can be useful for writing programs
• IDEs provide tools to aid writing and debugging
• IDEs can increase speed and reduce errors
• IDEs facilitate collaborative team working
• Merge Sort


  1. Splits the list in half repeatedly until it is in independent arrays / elements

  2. Compare the first two items and combine to create a new array in descending order

  3. Repeat with the next pairs of elements

  4. Compare the first element in the first two new arrays, choose the largest element, writing this to the new array first

  5. Repeat until no elements left

  6. Combine the two remaining lists into one list
• Merge Sort vs Insertion 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
• Data mining can be used to extract useful information from large datasets
• Data mining can be used in a variety of applications such as customer segmentation, fraud detection, and predictive maintenance
• Effective data mining requires careful data preparation, model selection, and evaluation
• Merge sort


  1. Might create a new array each time it splits and merges

  2. Often implemented recursively which places additional data on the stack
• Insertion sort


  1. Does not use any additional arrays

  2. Insertion sort is an in-place algorithm
• Caching


  • Data that has been used is stored in cache/RAM in case it is needed again
  • Allows faster access for future use
• Reusable components


  • One piece of code can be used in multiple places / called many times
  • Use of subroutines / procedures / functions
  • Use of classes
  • Use of external libraries
• Abstraction


  • Remove unnecessary details
  • Remove the outside world
  • Simplify real-life objects
• Concurrency


  • Multiple processes being executed at the same time
  • Giving processes a slice of the processor time
  • Having multiple processors each carrying out a different process
• Concurrency issues


  • Large number of requests to the server at a time
  • Server needs to respond in reasonable time
  • Having multiple processors handling the different requests would increase response time
  • Users could override each other's changes
  • Use record locking to stop edits if someone else has access to data
  • Different users will have different response times
  • Processor can still handle other requests so performance for other users is not affected
• Heuristic


  • 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
• Handling concurrent edits


  1. Increase response time

  2. Users could override each other's changes

  3. Needs to handle if someone updates their circus while someone else is visiting

  4. Use record locking to stop edits if someone else has access to data

  5. Different users will have different response times

  6. Processor can still handle other requests

  7. Performance for other users is not affected
• Heuristic


  An estimate or guess that estimates the distance or cost from each node to the destination node to speed up the process of finding a solution
• Final path = A,C,D,F,G and Distance = 110
• Breadth-first search


  1. Visit root node M

  2. Visit E and S

  3. Visit C and J (from E)

  4. Visit P and V (from S)

  5. Visit G and K (from J)

  6. Visit L (from K)
• Data mining


  • Searches large amounts of data
  • Searches for relationships between facts/components/events that may not be obvious
  • May include pattern matching algorithms
  • May involve anomaly detection algorithms
  • Used for business modelling
  • Used to plan for future eventualities
• Binary search


  • Compares the search value to the middle element
  • If the search value is less than the middle element, the left half of the array is searched
  • If the search value is greater than the middle element, the right half of the array is searched
  • This process is repeated until the search value is found or the array is exhausted
• Linear search


  Sequentially checks each element of the list until the target element is found or the entire list has been searched
• Time complexity


  • Worst-case space complexity
  • Best-case space complexity
  • Average time complexity