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

#include <cstdint>
// Return the sum of all values from 1 to n.
uint64_t add_to(uint32_t n) {
    uint64_t sum = 0;
    for (uint32_t i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

What is wrong with the above naive implementation?

The asymptotic performance is $O(n)$

$O(1)$ - Constant Time Implementation

#include <cstdint>
// Return the sum of all values from 1 to n.
uint64_t add_to(uint32_t n) {
  // avoid doubles as they cannot represent numbers close to UINT_MAX correctly
  if (n % 2) return ((n + 1ull) / 2) * n;
  return (n / 2 * (n + 1ull));
}

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

clang++ sum_to.cpp -o sum_to
time ./sum_to n
time ./sum_to 1

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)$
  • ...

Bubble Sort

Repeatedly step through the list, compare adjacent elements and swaps them

Bubble sort animation

Bubble-sort with Hungarian ("Csángó") folk dance

Exercise: implement the bubble sort algorthm
void bsort(int* array, size_t cnt)

Although simple, it is not used in practice due to the slow $O(n^2)$ performance.

Use the standard library

In practice, don't implement your own search

#include <algorithm>  // std::sort
#include <iostream>
#include <vector>


int main () {
  std::vector<int> values{ 33, 12, 99, 90, 7, 45 };
  std::sort(values.begin(), values.end());
  for (const auto& value : values) {
     std::cout << value << " ";
  }
  std::cout << std::endl;
  return 0;
}