Data Structures and Algorithms in C++

Introduction

Gerald Senarclens de Grancy

Terminology

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

Importance of Algorithms

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?

Download sum_to.cpp
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

Big O notation

  • 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

O(1)<O(log(n))<O(n)<O(nlog(n))<O(n2)<O(nk) for k>2

O(nk)<O(cn) for c>1

O(cn)<O(n!)

Basic Rules

O(kn)=O(n)

O(3n+5n2)=O(3n)+O(5n2)=O(n)+O(n2)=O(n2)

O(n2)+O(en)=O(en)

Counting Examples

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

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

Sorting

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(n2) 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;
}
Download sort.cpp

Questions
and feedback...