Prerequisites for Data Structures and Algorithms with C

In this course every structure is built in C with memory managed by hand: a node is defined with struct, allocated with malloc, linked with pointers, and given back with free when it is no longer needed. You should therefore be able to read C's types, pointers, arrays, and dynamic memory comfortably before starting. Comparing costs also takes a little mathematics: logarithms, summation formulas, and induction.

Each card gives a short summary of the topic, a small C example, and a check question; the answer is in the collapsible box under the question. The links go to the slides where the topic is used in the course.

Suggested order of preparation

Types and functions→ Pointers→ Arrays and strings→ struct→ Dynamic memory→ Recursion→ Logarithms and sums→ Big O

C fundamentals

Basic Types and sizeof

int, char, double · integer division · number of bytes

In C every variable has a type and occupies a definite number of bytes in memory; sizeof gives that number at compile time. Division between two integers is integer division: the fractional part is discarded. Array indices, the parent index in a heap (i / 2), and the midpoint in binary search all rely on this rule.

int a = 7, b = 2;
printf("%d\n", a / b);           /* 3   */
printf("%d\n", a % b);           /* 1   */
printf("%.1f\n", (double)a / b); /* 3.5 */
printf("%zu\n", sizeof(int));    /* 4 on most systems */

Check question: What is the value of m after the line double m = 7 / 2;?

Answer

3.0. The division is carried out between two int values, so the result is first 3 and is then converted to double. To get 3.5, at least one operand must be a double: 7.0 / 2.

Functions and Call by Value

parameter · return value · copy

In C all arguments are passed by value: the function receives a copy of the caller's variable. A function that wants to swap two variables must therefore take their addresses, not the variables themselves. In the course, swap, the top counter of a stack, and insertion into a search tree all take addresses for this reason.

void swap_wrong(int x, int y) { int t = x; x = y; y = t; }
void swap(int *x, int *y)      { int t = *x; *x = *y; *y = t; }

int a = 1, b = 2;
swap_wrong(a, b);   /* a == 1, b == 2: only the copies changed */
swap(&a, &b);       /* a == 2, b == 1 */

Check question: Although the three assignments inside swap_wrong run, why does a in main not change?

Answer

x and y are separate local variables initialized with the values of a and b when the function is called. The assignments change only these copies, and the copies disappear when the function returns.

Arrays and Strings

contiguous memory · char array ending in '\0'

An array is a block in which elements of the same type sit one after another in memory; access a[i] takes O(1), and C does no bounds checking. Passing an array to a function means passing the address of its first element; the size must be passed separately. A string is a char array that ends with '\0': "dog" occupies four bytes.

int sum_array(const int a[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++) s += a[i];
    return s;
}
int length(const char *s) {
    int n = 0;
    while (s[n] != '\0') n++;
    return n;
}
/* sum_array((int[]){4, 5, 6}, 3) == 15, length("dog") == 3 */

Check question: For the definition char s[] = "data";, do sizeof s and length(s) give the same value?

Answer

No. sizeof s is 5 bytes, including the final '\0'; length(s) counts up to the '\0' and returns 4.

struct and typedef

record · dot and arrow operators · self-referential structure

A struct gathers fields of different types into a single record; typedef gives the type a short name. A field is reached with . through a variable and with -> through a pointer; writing p->data is the same as (*p).data. The node of a linked list is a self-referential struct that carries a pointer to its own type.

typedef struct node *node_ptr;
typedef struct node {
    int data;
    node_ptr link;       /* next node or NULL */
} node;
node d = { 3, NULL };
node_ptr p = &d;
p->data = 8;             /* d.data is now 8 */

Check question: Can a structure directly contain a field of its own type (struct node next;)?

Answer

No. Such a structure would have infinite size. A structure can refer to its own type only through a pointer, and the size of a pointer is fixed.

Macros and Header Files

#define · #include · opaque type

The preprocessor substitutes macros defined with #define as text before compilation, which is why macro parameters are written inside parentheses. A header file (.h) carries the interface of a module and the .c file carries its implementation. If the header declares only typedef struct fraction Fraction;, the inside of the structure is hidden from the user: this is an opaque type and is the C counterpart of an abstract data type.

/* fraction.h */
#ifndef FRACTION_H
#define FRACTION_H
typedef struct fraction Fraction;     /* opaque: fields are not visible */
Fraction *fraction_create(int num, int den);
void      fraction_destroy(Fraction *f);
#endif
#define SQUARE(x) ((x) * (x))         /* SQUARE(1 + 2) == 9 */

Check question: If the macro were written as #define SQUARE(x) x * x, what would SQUARE(1 + 2) be?

Answer

5. It expands as text to 1 + 2 * 1 + 2, and the multiplication is done first. This is why the parameters and the whole expression must be put in parentheses.

bool and enum

<stdbool.h> · true/false · named constants

Since C99, the header <stdbool.h> provides the bool type and the constants true and false; in the course, insertion and deletion functions report with bool whether the operation succeeded. In conditions C still looks at integers: 0 is false and every nonzero value is true. An enum gives names to a group of integer constants; the first name gets the value 0 and the following ones increase by one. Operator kinds and node labels can thus be written with readable names instead of numbers.

#include <stdbool.h>
typedef enum { white, gray, black } color;   /* 0, 1, 2 */
bool is_empty(int n) { return n == 0; }
color c = gray;
printf("%d %d\n", c, is_empty(0));           /* 1 1 */

Check question: In the definition enum { lparen, rparen, plus, minus, times };, what value does times get?

Answer

4. Counting starts at 0: lparen is 0, rparen 1, plus 2, minus 3, times 4.

Recursion and the Call Stack

base case · stack frame · stack overflow

A function that calls itself must make the problem smaller at every call and must reach a base case. For every call, a frame holding the local variables and the return address is added to the call stack; if the depth is n, the extra memory is O(n). Tree traversals, binary search, the towers of Hanoi, and quicksort are written in this style.

long fact(int n) {
    if (n <= 1) return 1;        /* base case */
    return n * fact(n - 1);      /* smaller problem */
}
/* fact(4) -> 4 * fact(3) -> 4 * 3 * fact(2)
           -> 4 * 3 * 2 * fact(1) = 24 */

Check question: When fact(4) is called, what is the largest number of fact frames on the call stack at the same time?

Answer

Four: fact(4), fact(3), fact(2), and fact(1). No frame is closed before fact(1) returns.

Pointers and memory

Pointers

& and * · NULL · alias

A pointer is a variable that holds the address of an object. &x gives the address of x, and *p reaches the object that p points to. NULL is a pointer that points nowhere and, in the course, represents the empty list and the empty subtree. Two pointers can point to the same object; a change made through one is visible through the other.

int x = 5;
int *p = &x;     /* p holds the address of x */
int *q = p;      /* q also points to x       */
*q = 7;          /* x == 7, *p == 7          */
p = NULL;        /* p now points nowhere; x is still 7 */

Check question: After the last line, what is the value of the expression *q?

Answer

7. p = NULL changes only the variable p; q still points to x.

Array and Pointer Arithmetic

a[i] == *(a + i) · counts elements, not bytes

Inside an expression, the name of an array turns into the address of its first element. Adding 1 to a pointer advances it to the next element, not by one byte: if int is 4 bytes, the address grows by 4. By definition, a[i] means *(a + i). The row-major address computation for multidimensional arrays rests on the same rule.

int a[] = {10, 20, 30, 40};
int *p = a;               /* p == &a[0] */
printf("%d\n", *(p + 2)); /* 30 */
p++;                      /* p == &a[1] */
printf("%d\n", p[1]);     /* 30: p[1] == a[2] */
printf("%td\n", &a[3] - p);  /* 2 elements */

Check question: If int is 4 bytes and the array a starts at address 1000, which address does a + 3 point to?

Answer

1012. The address advances by 3 elements, that is 3 · 4 = 12 bytes.

Dynamic Memory

malloc · calloc · realloc · free

Local variables disappear when the function ends; a block obtained with malloc lives in heap memory until free is called. malloc returns NULL if memory runs out, so its return value is checked every time. A block that is never returned causes a memory leak, and a pointer that is used after the block has been returned is a dangling pointer.

int n = 5;
int *a = malloc(n * sizeof *a);
if (a == NULL) return 1;          /* out of memory */
for (int i = 0; i < n; i++) a[i] = i * i;
int *b = realloc(a, 2 * n * sizeof *a);  /* grow */
if (b == NULL) { free(a); return 1; }
a = b;
free(a);
a = NULL;                         /* leave no dangling pointer */

Check question: Why does writing a = realloc(a, new_size); cause a leak if realloc fails?

Answer

On failure realloc returns NULL and the old block stays where it was. If the result is written straight into a, the address of the old block is lost and the block can never be freed. The result must first be kept in a separate pointer, as in the example.

Pointer to Pointer

changing the head of a list · &root

If a function is going to change the caller's pointer (for example the head of a list or the root of a tree), it must receive the address of that pointer. The type is then node **. This is the call-by-value rule applied to pointers: a pointer is also a variable and is passed by copy.

void insert_front(node_ptr *head, node_ptr item) {
    item->link = *head;   /* the new node points to the old head */
    *head = item;         /* the caller's head pointer changes */
}
node_ptr list = NULL;
insert_front(&list, p);   /* list now points to p's node */

Check question: Suppose the function were written as void insert_front(node_ptr head, node_ptr item) and ended with head = item;. If the list is empty, what would list be after the call?

Answer

It would stay NULL. head is a copy of list; assigning to the copy does not affect the caller, and no pointer would be left to the new node.

Function Pointers and qsort

void * · comparison function

The name of a function is also an address and can be passed to another function as an argument. qsort in the standard library works without knowing the element type: it takes the array as void * and asks the user's comparison function for the order of two elements. The function returns a negative number, zero, or a positive number.

int ascending(const void *x, const void *y) {
    int a = *(const int *)x, b = *(const int *)y;
    return (a > b) - (a < b);   /* -1, 0 or 1 */
}
int d[] = {37, 15, 24};
qsort(d, 3, sizeof d[0], ascending);   /* d: 15 24 37 */

Check question: In which case does the shortcut return a - b; give a wrong result in the comparison?

Answer

When the difference overflows the int range, for example when a is a very large positive number and b a very large negative one. Overflow is undefined behavior and the sign can come out reversed; (a > b) - (a < b) does not carry this risk.

Mathematics

Exponents and Logarithms

lg n = log₂ n · repeated halving

In the course, lg n is the logarithm to base 2: it tells how many times n must be halved to reach 1. Since 2¹⁰ = 1024 ≈ 10³, lg n ≈ 20 for a million elements. This is why binary search, the height of a balanced tree, and heap operations take O(lg n). The base of the logarithm changes only a constant factor; the base is not written inside big O.

int halvings(int n) {
    int k = 0;
    while (n > 1) { n /= 2; k++; }
    return k;                     /* ⌊lg n⌋ */
}
/* 1 → 0, 8 → 3, 1000 → 9, 1024 → 10 */

Check question: If a sorted array has 1,000,000 elements, about how many comparisons does binary search make at most?

Answer

About 20. Since 2²⁰ = 1,048,576 ≥ 1,000,000, the range shrinks to a single element in at most 20 halvings.

Summation Formulas

arithmetic and geometric series

The cost of nested loops is very often a sum. Two formulas are used constantly in the course: 1 + 2 + … + n = n(n + 1)/2 and 1 + 2 + 4 + … + 2ᵏ = 2ᵏ⁺¹ − 1. The first shows that selection sort and insertion sort are O(n²); the second shows that a binary tree of depth k has at most 2ᵏ − 1 nodes and that the total number of copies in an array whose capacity doubles stays O(n).

int count = 0;
for (int i = 0; i < n - 1; i++)       /* selection sort */
    for (int j = i + 1; j < n; j++)
        count++;                      /* one comparison */
/* count == (n-1) + (n-2) + ... + 1 == n(n-1)/2
   10 for n = 5 */

Check question: An array starts with capacity 1 and doubles every time it fills up. If 16 elements are added, how many elements are copied in total during the growths?

Answer

15. The growths happen when 1, 2, 4, and 8 elements are in the array: 1 + 2 + 4 + 8 = 2⁴ − 1 = 15. A constant number of copies falls on each element.

Induction

base step · inductive step

If a statement is true for n = 1 (the base step) and its truth for n − 1 implies its truth for n (the inductive step), then it is true for all n ≥ 1. The correctness of a recursive function is proved the same way: the base case gives the right result, and if the smaller calls are right, the larger call is right too. Lemmas on the number of nodes in trees are proved with this method.

/* Claim: total(n) == n * (n + 1) / 2 */
int total(int n) {
    if (n == 0) return 0;            /* base: 0 == 0·1/2 */
    return total(n - 1) + n;         /* (n-1)n/2 + n == n(n+1)/2 */
}

Check question: In proving that level i of a binary tree has at most 2ⁱ⁻¹ nodes, which observation is used in the inductive step?

Answer

Every node has at most two children. If level i − 1 has at most 2ⁱ⁻² nodes, then level i can have at most 2 · 2ⁱ⁻² = 2ⁱ⁻¹ nodes.

Modular Arithmetic

% operator · circular index · hashing

x % m is the remainder of dividing x by m and stays between 0 and m − 1 for nonnegative x. In a circular queue, an index that reaches the end of the array wraps around to the start with (rear + 1) % MAX; in a hash table, k % m maps a key to a bucket. In C the remainder of a negative number can be negative, which is why unsigned types are used in hash computations.

#define MAX 5
int rear = 4;
rear = (rear + 1) % MAX;     /* 0: wrapped around to the start */
unsigned h(unsigned k, unsigned m) { return k % m; }
/* m = 13: h(27, 13) == 1, h(40, 13) == 1 → collision */

Check question: For m = 13, which buckets do the keys 18 and 44 fall into?

Answer

18 % 13 = 5 and 44 % 13 = 5 (44 = 3 · 13 + 5). Both fall into the same bucket; this is a collision.

Counting: Factorials and Subsets

n! · 2ⁿ · the limit of brute force

n elements have n! different orderings and 2ⁿ different subsets. Brute-force algorithms try all of these; generating permutations takes O(n · n!), and generating subsets or trying a SAT instance takes O(2ⁿ). Both 2ⁿ and n! grow so fast that even the fastest machine is not enough at about n = 20 for n! and n = 60 for 2ⁿ; this is why backtracking and a good algorithm matter.

/* all subsets of n elements: each bit is one element */
for (unsigned m = 0; m < (1u << n); m++) {
    for (int i = 0; i < n; i++)
        if (m & (1u << i)) printf("%d ", a[i]);
    printf("\n");
}   /* 8 lines for n = 3, the first is the empty set */

Check question: How many different permutations does the string "abcd" have, and how many letters are printed for each?

Answer

4! = 24 permutations, each printing 4 letters; 96 letters in total. This is why generating permutations takes O(n · n!).

Matrices and Two-Dimensional Arrays

row-major storage · transpose · product

An m × n matrix is held in C as int a[M][N] and stored in row-major order: a[i][j] is i·N + j elements away from the start of the array. The transpose turns rows into columns: Aᵀ[j][i] = A[i][j]. The product of an m × n matrix and an n × p matrix is m × p; each element is the inner product of a row and a column, and three nested loops make m·n·p multiplications in total. Sparse matrices, the adjacency matrix of a graph, and all-pairs shortest paths are written with these operations.

/* c = a × b : a is M×N, b is N×P, c is M×P */
for (int i = 0; i < M; i++)
    for (int j = 0; j < P; j++) {
        c[i][j] = 0;
        for (int k = 0; k < N; k++)
            c[i][j] += a[i][k] * b[k][j];
    }

Check question: A is 2 × 3 and B is 3 × 4. How many elements does AB have, and how many multiplications does computing it take?

Answer

AB has 2 × 4 = 8 elements. Each element is a sum of 3 products; 2 · 3 · 4 = 24 multiplications are made in total.

Basic Probability and Expected Value

uniform distribution · average case · load factor

Average-case analysis is done under the assumption that the input or the hash values are randomly distributed. The expected value of a quantity is the sum of each value it can take multiplied by its probability; the expected value of a sum is the sum of the expected values of its terms. In sequential search, if the sought element is equally likely to be at any position, the average is (n + 1)/2 comparisons. If n keys are spread uniformly over m buckets, the expected number of keys in a bucket is n/m; this ratio is the load factor α of the hash table.

/* if the item is at position k, k comparisons; each position has probability 1/n */
double avg = 0;
for (int k = 1; k <= n; k++)
    avg += k * (1.0 / n);
/* avg == (n + 1) / 2.0 ; 5 for n = 9 */

Check question: 25 keys are uniformly distributed in a chained hash table with 10 buckets. What is the load factor, and how many nodes does an unsuccessful search walk on average?

Answer

α = 25/10 = 2.5. An unsuccessful search walks the whole chain that the key falls into; since the expected length of a chain is α, 2.5 nodes are examined on average.

Sets and Relations

union · disjoint sets · equivalence classes

A set is a collection of distinct elements; the union (A ∪ B) gives all elements of the two sets, and the intersection (A ∩ B) gives the common elements. Sets whose intersection is empty are called disjoint. A relation is an equivalence relation if it is reflexive (x ≡ x), symmetric (if x ≡ y then y ≡ x), and transitive (if x ≡ y and y ≡ z then x ≡ z); it divides its elements into disjoint equivalence classes. The union-find structure keeps these classes; Kruskal's algorithm also uses the same structure to ask whether two vertices are in the same component.

/* elements 0..4; declarations: 0 ≡ 2, 3 ≡ 4, 2 ≡ 1 */
/* classes: {0, 1, 2} and {3, 4} */
int representative[5] = {0, 0, 0, 3, 3};
bool same_class(int x, int y) {
    return representative[x] == representative[y];
}   /* same_class(1, 0) == true, same_class(1, 4) == false */

Check question: Is “being born in the same year” an equivalence relation? What about the relation “x is less than y”?

Answer

The first is an equivalence relation: it is reflexive, symmetric, and transitive, and its classes are the birth years. The second is not: it is not reflexive because no number is less than itself, and it is not symmetric because x < y rules out y < x.

Introduction to algorithm analysis

Counting Steps

program step · number of loop iterations

The time of an algorithm is measured by how many basic steps it runs as a function of the input size n. Every assignment, comparison, and return counts as one step; the condition of a loop is checked once more than the body runs. Constants are details; what matters is how the number of steps grows with n.

float sum(float list[], int n) {
    float t = 0;                  /* 1 step      */
    for (int i = 0; i < n; i++)   /* n + 1 steps */
        t += list[i];             /* n steps     */
    return t;                     /* 1 step      */
}                                 /* total 2n + 3 */

Check question: A function adds two m × n matrices with two nested loops. Which term does its number of steps grow with?

Answer

With the term m · n. The inner body runs m · n times; the loop checks add only smaller terms, so the result is O(m · n).

Big O, Ω, and Θ

upper bound · lower bound · tight bound

f(n) = O(g(n)) says that there is a positive constant c such that f(n) ≤ c · g(n) for every sufficiently large n: g is an upper bound for f. Ω is the lower bound, and Θ shows that both hold together. The usual order is 1 < lg n < n < n lg n < n² < n³ < 2ⁿ < n!.

/* for T(n) = 3n² + 6n + 7:
   for n ≥ 1, 6n ≤ 6n² and 7 ≤ 7n², so
   T(n) ≤ 3n² + 6n² + 7n² = 16n²  →  T(n) = O(n²)
   T(n) ≥ 3n²                      →  T(n) = Ω(n²)
   both together                   →  T(n) = Θ(n²) */

Check question: Is it wrong to write 2n + 3 = O(n²)?

Answer

It is not wrong; O says only an upper bound, and n² is above 2n + 3. But it is uninformative: the tight bound is Θ(n), and in analysis the smallest upper bound is sought.

Best, Average, and Worst Case

input-dependent time · amortized cost

Two inputs of the same size may be processed in different amounts of time. In linear search, one comparison suffices if the sought element is first (best case), and n comparisons are needed if it is absent (worst case). The average case requires an assumption about the distribution of inputs. Amortized analysis looks not at single operations but at the total cost of a sequence of operations.

int linear_search(const int a[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (a[i] == x) return i;   /* found */
    return -1;                     /* absent: n comparisons */
}

Check question: If the sought element is in the array and is equally likely to be at any position, how many comparisons does linear search make on average?

Answer

(1 + 2 + … + n) / n = (n + 1) / 2. The average case is also Θ(n).

Recurrence Relations

running time of recursive algorithms

The running time of a recursive algorithm is written in terms of itself and solved by expansion. An algorithm that halves the problem at each step and does constant work runs in O(lg n) with T(n) = T(n/2) + c (binary search). An algorithm that solves two halves and combines them with linear work runs in O(n lg n) with T(n) = 2T(n/2) + cn (merge sort). In the towers of Hanoi, the relation h(n) = 2h(n − 1) + 1 gives 2ⁿ − 1.

int binary_search(const int a[], int left, int right, int x) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (a[mid] == x) return mid;
    if (a[mid] < x) return binary_search(a, mid + 1, right, x);
    return binary_search(a, left, mid - 1, x);
}   /* T(n) = T(n/2) + c  →  O(lg n) */

Check question: Which growth class does the relation T(n) = T(n − 1) + n (with T(1) = 1) belong to?

Answer

Θ(n²). Expanded, T(n) = n + (n − 1) + … + 1 = n(n + 1)/2. Recursions that eliminate only one element at each step give this relation; the worst case of quicksort is like this too.

Space Complexity and Measurement

extra memory · timing with clock()

Space complexity measures the extra memory needed beyond the input: summing with a loop is O(1), while doing the same work with recursion takes O(n) space on the call stack. Theoretical analysis is also tested with real measurement: clock() gives the processor time the program has used. Short tasks are measured by repeating them many times, and slow input and output operations such as printf are kept outside the measured region.

#include <time.h>
clock_t start = clock();
for (int t = 0; t < 1000; t++)
    linear_search(a, n, -1);        /* worst case */
double sec = (double)(clock() - start) / CLOCKS_PER_SEC;
printf("%g s per search\n", sec / 1000);

Check question: If the measured time grows about fourfold when n doubles, what can be said about the growth of the algorithm?

Answer

The time most likely grows with n²: (2n)² = 4n². For a linear algorithm the time would only double.

The code examples are written for C99 and assume that int is 4 bytes. The types node and node_ptr used in the examples are defined in the “struct and typedef” card.

Sercan KÜLCÜ, All rights reserved.