Algorithms on Sequential Data

Related Data Structures

• C array
• C string
• C++ string
• STL containers: std::vector, std::array, std::list, etc.

Search

• Linear search
• Binary search
• Sub-sequence search
• Variations
  • duplicate elements
  • first/last/all occurrence(s)
  • count

Aggregate Functions

Calculate a single value from a sequence (aggregation). A lot of statistical functions fall into this category.

• Count
• Summation
• Average
• Median
• Mode
• Standard Deviation

Map/Filter Functions

• Map: Apply an operation on every element
  • make all elements positive
• Filter: Keep a subset of elements according to some rule (will be discussed in the vector chapter)
  • filter negative values
  • filter all odd values

Compare

• array/string comparison

Simple Sorting Algorithms

• selection sort

  Repeatedly select the minimum element from the unsorted part and put it at the beginning of the unsorted part. Assuming ascending order.

• insertion sort

  Elements in the unsorted part are repeatedly inserted to the correct position in the sorted part.