Data Structure

• Stores and organizes data so that it can be used efficiently
• http://en.wikipedia.org/wiki/Data_structure

Algorithm

• Procedure or formula for solving a problem
• Finite series of computational steps to produce a result
• Independent from any programming language
• Examples for basic algorithms: sorting and searching
• Brute force algorithm: performs an exhaustive search of all possible solutions

Complexity

• Measure of the difficulty of constructing a solution to a problem
• Estimate of the number of operations needed to execute an algorithm

Big O notation

• Asymptotic notation
• Estimates the worst case performance of data structures and algorithms
• http://en.wikipedia.org/wiki/Big_O_notation

Introductory Example

Calculating the sum of all numbers ≤ n

def add_to(n):
    """
    Return the sum of all values from 1 to n.
    """
    sum = 0
    for i in range(n+1):
        sum += i
    return sum

What is wrong with the above naive implementation?

The asymptotic performance is $O(n)$

$O(1)$ - Constant Time Implementation

# after refacturing
def add_to(n):
    """
    Return the sum of all values from 1 to n.
    """
    return n * (n + 1) // 2

Which impact can $O(1)$ vs $O(n)$ have?

time python sum_to.py linear
time python sum_to.py constant

Why Are Algorithms More Important Than Ever?

Despite computers being faster than ever, why are data structures and algorithms still important, even more so than in the past?

Because computers have to deal with larger amounts of data.

Computation time costs energy

• Analyzes the worst case memory usage/ runtime of algorithms
• Big O provides an upper bound
• History
  • First introduced by number theorist Paul Bachmann in 1894
  • Popularized in the work of number theorist Edmund Landau (Landau symbol)
  • Donald Knuth popularized the notation in computer science

Problem Classes

• Constant
• Logarithmic
• Linear
• Loglinear
• Polynomial
• Exponential
• Factorial

Orders of Common Problem Classes

Basic Rules

Counting Examples

How many steps are required, at most, for the following tasks?

• Calculate the sum of all elements in a collection
• Shake each other's hands
• Calculate the third power of each element in a $n\times n$ square matrix
• Solve a TSP (brute force)
• Sort an array (see next slide)

• The fastest sorting algorithms are log-linear $O(n\ast \log n)$
• For pre-sorted data, performance may even be linear
• Multiple sorting algorithms exist:
  • Bubble sort - $O(n^2)$
  • Merge sort - $O(n\log n)$
  • Quicksort - $O(n\log n)$
  • Timsort - $O(n\log n)$
  • ...