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

// Return the sum of all values from 1 to n.
unsigned long long add_to(unsigned n) {
unsigned long long sum = 0;
for (unsigned 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

// Return the sum of all values from 1 to n.
unsigned long long add_to(unsigned n) {
return (unsigned long long) ((n / 2.0 * n) + (n / 2.0));
}

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

Download sum_to.c
clang sum_to.c -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)

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.

qsort

In practice, don't implement your own search. Use the standard library.

#include <stdio.h>
#include <stdlib.h> // qsort
int compare (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int main () {
int values[] = { 33, 12, 99, 90, 7, 45 };
qsort (values, 6, sizeof(int), compare);
for (size_t n=0; n<6; ++n) {
printf ("%d ",values[n]);
}
printf("\n");
return 0;
}
Download qsort.c

Questions
and feedback...