Programming Patterns and Algorithms:

Algorithmic components that frequently reappear/get reused.

• Continue if you please: This pattern executes a given algorithm once and then prompts the user to either exit or re-execute the algorithm (with different inputs?). The heart of this component is a loop that always executes at least once.
  
  
• Search for optimal/Examine all: This pattern exhaustively examines every element in a list (or set) seeking some optimal value. (i.e. largest, smallest, most profitable.) The heart of this pattern is "seeding" the best-seen-to-date with the value of the first element in the set/list.
  

  One should also be familiar with how to short circuit the examine all pattern. The best example of this is the "Short Sequential Search." Algorithms of this type typically run in linear time.
  
  

• 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. These algorithms typically have a logarithmic running time
  
  
• All-Pairs: This pattern compares/examines each element of a set/list with each other element of the list/set. The heart of the pattern is a pair of nested for loops; the outer iterating over the complete set/list, the inner iterating from one plus the outer loop index to the end of the set/list. Typically all-pairs algorithms run in quadratic (n²) time.
  
  
• Acquiring User Input: There are number of ways to acquire user input:
  • Fixed number of values: The number of input values to be input can be known a priori or initially input by the user. In either case a simple FOR loop is sufficient to acquire the user input.
  • Variable number of values: The number of input values is unknown, but the user will enter a sentinel value to signal completion. A WHILE loop is used with a prompt for input immediately prior to the WHILE loop and another input prompt at the very end of the WHILE loop's body. The WHILE loop tests the input for the terminating condition.
• Acceptance testing: Given a list and a condition, one wishes to determine if the condition holds true over the complete list. Be optimistic! Set a boolean flag initialized to TRUE. Process the list with a WHILE loop that iterates while there are elements left to process AND the flag is TRUE. Each iteration of the loop checks an individual list element against the condition, setting the flag to FALSE if appropriate. (The solution to the palindrome lab 5 assignment illustrates this pattern.)
  
  
• Iterate over the contents of an aggregate (collection): Given an aggregate, iterate over each value in the aggregate. This is often used in conjunction with "Examine All." Aggregate iteration is its own entry due to the special nature of using an Iterator in Java.