ICS4U Grade 12 – Computer Science – Advanced Algorithms Test

Grade 12 – Computer Science

 

Advanced Algorithms – A Guide to Programming in Java Ch 13

 

Selection Sort

  • Sorts by finding the lowest number and swapping it with first
  • Next, it will look at the list from the 2nd number onwards and look for the lowest number from there
  • It will find the smallest number from 2 till the end, and swap it with the 2nd number
  • Nested for-loops are capable of doing this method, without the use of recursions

 

Sorting Objects

  • Using the equals() or compareTo() implemented in objects, you may compare objects
  • Objects may also implement the Comparable Interface to use to compare
  • Interfaces cannot be used to instantiate a class but interfaces can be used as a data type.
  • Interface data type can refer to any class it implements
  • This polymorphic behavior can allow a generic sort of any list of objects which have the Comparable Interface

 

Insertion Sort

  • Starts sorting with the first 2 items in a list, shifts them to the correct place
  • The third item will be compared and shifted up to where it fits
  • Each element is compared with all the elements before it to see where it should fit

 

Recursion

  • Recursive Call: are methods that can call itself.
  • A recursive method calls itself but with different parameters each time
  • Recursion can be used to solve problems requiring smaller versions of the same problem, then combining the results
    • For example, if we wanted to use recursion to find the value of a number raised to a power, we could have a recursion call that reduces the number into x * xn-1 each time until it reaches 1 and adding all the results.
    • 23 is 2* 22 + 2* 21 + 1 which is 8
      • Each 2* 23 is a new call in the recursive method

 

Mergesort

  • Selection short is inefficient for large arrays
  • Merge sort takes a “divide-and-conquer” approach in sorting numbers.
  • It cuts the array in half, and cuts the halfs in half and so on to to sort smaller sections
  • Mergesort will then recombine all of the elements together into one large sorted array
  • Mergesort has a recursive method that keeps calling itself to sort the halves
  • A temporary array is needed to store the items moved from two sorted arrays into the items array

 

Binary Search

  • Binary search uses a sorted list to quickly look for the location of a value
  • It too also takes the divide and conquer approach
  • It cuts the array in half and determines, by comparing the target value with the middle, beginning, and end value to see which half the value is located in
  • It then takes the half and does the same thing to cut that in half
  • Eventually, it will find the number on one of the halves
  • This saves time because it only looks at half of the values at a time, not needing to go through the entire array

 

Depth-First Searching

  • Solves problems, not sort lists
  • A problem is solvable with DFS If it can be modeled by a tree diagram
  • It looks deeper and deeper into the problem, in smaller chunks, until it finds the solution (uses recursive methods)
  • Each time a recursive method is called, it does the same actions differently with slight modifications to get deeper into the problem.
  • Can be used for solving mazes, creating schedules, or possible plays in a game