Algorithms and Algorithmic Patterns Carefully Studied

Algorithmic Patterns

• Examine All: Given a list of n values, the algorithm must examine each value in the list.
  
  Examples of this pattern are: Sequential Search, Find Largest, Find 2nd Largest, Fibonacci List Checker , and Longest Sorted Subsequence.
  
  Examine All algorithms typically run in time O(n)



• All Pairs: Given a list of n values, each element of the list is processed against/with every other element in the list. One can extrapolate this pattern to two lists: each value in the first list is compared against each element in the second list.
  
  Examples of this pattern are: List Intersection, Duplicates, Sums to X, Sums to X, and the Foobar list checker algorithm developed in class.
  
  All Pairs algorithms typically run in time O(n²)



• Divide and Conquer: Given a list of n values, the algorithm repeatedly divides the list into halves and continues to work toward the solution using one of the two halves.
  
  Binary Search is an example of a divide and conquer algorithm. (Binary Search implemented in the Digital Computer Assembly Language.)
  
  These algorithms typically have a logarithmic running time.

Algorithms

Searching Algorithms

• Sequential Search: Find a specified value from an unordered list.



• Short Sequential Search: Find a specified value from an already ordered list.



• Binary Search: Find a specified value from an already ordered list.



• Find Largest: Find the maximum (minimum) value and its location from an unordered list. One can also use the findLargest algorithm to find the 2nd largest value in a list, or even for finding the median value in a list.



• Max-Min Find: Find both the maximum and minimum value, and their respective locations, from an unordered list.

Sorting Algorithms

• Selection Sort



• Insertion Sort.

Hardware Algorithms

• Sum of Products: Given a truth table for a circuit, construct the actual circuit using only AND, OR, and NOT gates.