Data Structures and Algorithms Manual

This page provides code and pseudocode for all of the main data structures and algorithms discussed in COMP2521.

Contents

Search Algorithms

Linear search

int linearSearch(int arr[], int size, int val) {
	for (int i = 0; i < size; i++) {
		if (arr[i] == val) {
			return i;
		}
	}
	return -1;
}

Binary search

int binarySearch(int arr[], int size, int val) {
	int lo = 0;
	int hi = size - 1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		if (val < arr[mid]) {
			hi = mid - 1;
		} else if (val > arr[mid]) {
			lo = mid + 1;
		} else {
			return mid;
		}
	}
	return -1;
}

Sorting Algorithms

Macros

The code below uses these macros to compare items.

Note that these macros assume that the arrays contain integers - they would be defined differently when sorting other types of items.

#define lt(x, y) (x <  y) // less than
#define le(x, y) (x <= y) // less than or equal to
#define ge(x, y) (x >= y) // greater than or equal to
#define gt(x, y) (x >  y) // greater than

Selection sort

void selectionSort(Item items[], int lo, int hi) {
	for (int i = lo; i < hi; i++) {
		int min = i;
		for (int j = i + 1; j <= hi; j++) {
			if (lt(items[j], items[min])) {
				min = j;
			}
		}
		swap(items, i, min);
	}
}

Bubble sort

void bubbleSort(Item items[], int lo, int hi) {
	for (int i = hi; i > lo; i--) {
		bool swapped = false;
		for (int j = lo; j < i; j++) {
			if (gt(items[j], items[j + 1])) {
				swap(items, j, j + 1);
				swapped = true;
			}
		}
		if (!swapped) break;
	}
}

Insertion sort

void insertionSort(Item items[], int lo, int hi) {
	for (int i = lo + 1; i <= hi; i++) {
		Item item = items[i];
		int j = i;
		for (; j > lo && lt(item, items[j - 1]); j--) {
			items[j] = items[j - 1];
		}
		items[j] = item;
	}
}

Shell sort

void shellSort(Item items[], int lo, int hi) {
	int size = hi - lo + 1;
	int h;
	for (h = 1; h <= (size - 1) / 9; h = (3 * h) + 1);

	for (; h > 0; h /= 3) {
		for (int i = lo + h; i <= hi; i++) {
			Item item = items[i];
			int j = i;
			for (; j >= lo + h && lt(item, items[j - h]); j -= h) {
				items[j] = items[j - h];
			}
			items[j] = item;
		}
	}
}

Merge sort

void mergeSort(Item items[], int lo, int hi) {
	if (lo >= hi) return;
	int mid = (lo + hi) / 2;
	mergeSort(items, lo, mid);
	mergeSort(items, mid + 1, hi);
	merge(items, lo, mid, hi);
}

void merge(Item items[], int lo, int mid, int hi) {
	Item *tmp = malloc((hi - lo + 1) * sizeof(Item));

	int i = lo;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= hi) {
		if (le(items[i], items[j])) {
			tmp[k++] = items[i++];
		} else {
			tmp[k++] = items[j++];
		}
	}

	while (i <= mid) tmp[k++] = items[i++];
	while (j <= hi) tmp[k++] = items[j++];

	for (i = lo, k = 0; i <= hi; i++, k++) {
		items[i] = tmp[k];
	}

	free(tmp);
}

Quick sort

Naive quick sort
void naiveQuickSort(Item items[], int lo, int hi) {
	if (lo >= hi) return;
	int pivotIndex = partition(items, lo, hi);
	naiveQuickSort(items, lo, pivotIndex - 1);
	naiveQuickSort(items, pivotIndex + 1, hi);
}

int partition(Item items[], int lo, int hi) {
	Item pivot = items[lo];

	int l = lo + 1;
	int r = hi;
	while (true) {
		while (l < r && le(items[l], pivot)) l++;
		while (l < r && ge(items[r], pivot)) r--;
		if (l == r) break;
		swap(items, l, r);
	}

	if (lt(pivot, items[l])) l--;
	swap(items, lo, l);
	return l;
}
Median-of-three quick sort
void medianOfThreeQuickSort(Item items[], int lo, int hi) {
	if (lo >= hi) return;
	medianOfThree(items, lo, hi);
	int pivotIndex = partition(items, lo, hi);
	medianOfThreeQuickSort(items, lo, pivotIndex - 1);
	medianOfThreeQuickSort(items, pivotIndex + 1, hi);
}

void medianOfThree(Item a[], int lo, int hi) {
	int mid = (lo + hi) / 2;
	if (gt(a[mid], a[lo])) swap(a, mid, lo);
	if (gt(a[lo], a[hi])) swap(a, lo, hi);
	if (gt(a[mid], a[lo])) swap(a, mid, lo);
}

Radix sort

radixSort(A):
    Input: array A of keys
           where each key consists of m symbols
           from an "alphabet" of size R

    initialise R buckets // one for each symbol

    for i from m down to 1:
        empty all buckets
        for each key in A:
            append key to bucket key[i]

        clear A
        for each bucket (in order):
            for each key in bucket:
                append key to A

Abstract Data Types

Stack ADT

Interface
typedef struct stack *Stack;

typedef int Item;

/**
 * Creates a new empty stack
 */
Stack StackNew(void);

/**
 * Frees all memory allocated to the stack
 */
void StackFree(Stack s);

/**
 * Adds an item to the top of the stack
 */
void StackPush(Stack s, Item item);

/**
 * Removes an item from the top of the stack and returns it
 * Assumes that the stack is not empty
 */
Item StackPop(Stack s);

/**
 * Returns the number of items in the stack
 */
int StackSize(Stack s);

/**
 * Returns the item at the top of the stack without removing it
 * Assumes that the stack is not empty
 */
Item StackPeek(Stack s);
Implementation
struct stack {
	struct node *head;
	int size;
};

struct node {
	Item item;
	struct node *next;
};

Stack StackNew(void) {
	Stack s = malloc(sizeof(struct stack));
	if (s == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	s->head = NULL;
	s->size = 0;
	return s;
}

void StackFree(Stack s) {
	struct node *curr = s->head;
	while (curr != NULL) {
		struct node *temp = curr;
		curr = curr->next;
		free(temp);
	}
	free(s);
}

void StackPush(Stack s, Item item) {
	struct node *new = malloc(sizeof(struct node));
	if (new == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	new->item = item;
	new->next = s->head;

	s->head = new;
	s->size++;
}

Item StackPop(Stack s) {
	if (s->size == 0) {
		fprintf(stderr, "error: stack is empty!\n");
		return 0;
	}

	struct node *newHead = s->head->next;
	Item it = s->head->item;

	free(s->head);
	s->head = newHead;
	s->size--;

	return it;
}

int StackSize(Stack s) {
	return s->size;
}

Item StackPeek(Stack s) {
	if (s->size == 0) {
		fprintf(stderr, "error: stack is empty!\n");
		return 0;
	}

	return s->head->item;
}

Queue ADT

Interface
typedef int Item;

typedef struct queue *Queue;

/**
 * Creates a new empty queue
 */
Queue QueueNew(void);

/**
 * Frees all memory allocated to the queue
 */
void QueueFree(Queue q);

/**
 * Adds an item to the end of the queue
 */
void QueueEnqueue(Queue q, Item it);

/**
 * Removes an item from the front of the queue and returns it
 * Assumes that the queue is not empty
 */
Item QueueDequeue(Queue q);

/**
 * Returns the number of items in the queue
 */
int QueueSize(Queue q);

/**
 * Returns the item at the front of the queue without removing it
 * Assumes that the queue is not empty
 */
Item QueuePeek(Queue q);
Implementation
struct queue {
	struct node *head;
	struct node *tail;
	int size;
};

struct node {
	Item item;
	struct node *next;
};

static struct node *newNode(Item it);

Queue QueueNew(void) {
	Queue q = malloc(sizeof(struct queue));
	if (q == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	q->head = NULL;
	q->tail = NULL;
	q->size = 0;
	return q;
}

void QueueFree(Queue q) {
	struct node *curr = q->head;
	while (curr != NULL) {
		struct node *temp = curr;
		curr = curr->next;
		free(temp);
	}
	free(q);
}

void QueueEnqueue(Queue q, Item it) {
	struct node *n = newNode(it);
	if (q->size == 0) {
		q->head = n;
	} else {
		q->tail->next = n;
	}
	q->tail = n;
	q->size++;
}

static struct node *newNode(Item it) {
	struct node *n = malloc(sizeof(*n));
	if (n == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	n->item = it;
	n->next = NULL;
	return n;
}

Item QueueDequeue(Queue q) {
	if (q->size == 0) {
		fprintf(stderr, "error: queue is empty!\n");
		return 0;
	}

	struct node *newHead = q->head->next;
	Item it = q->head->item;

	free(q->head);
	q->head = newHead;
	if (newHead == NULL) {
		q->tail = NULL;
	}
	q->size--;

	return it;
}

int QueueSize(Queue q) {
	return q->size;
}

Item QueuePeek(Queue q) {
	if (q->size == 0) {
		fprintf(stderr, "error: queue is empty!\n");
		return 0;
	}

	return q->head->item;
}

Binary Search Trees

struct node {
	int value;
	struct node *left;
	struct node *right;
};

/**
 * Returns an empty BST
 */
struct node *bstNew(void) {
	return NULL;
}

/**
 * Frees all memory allocated to the BST
 */
void bstFree(struct node *tree) {
	if (tree == NULL) {
		return;
	}

	bstFree(tree->left);
	bstFree(tree->right);
	free(tree);
}

/**
 * Inserts a value into the BST and returns the root of the udpated BST
 */
struct node *bstInsert(struct node *tree, int val) {
	if (tree == NULL) {
		return newNode(val);
	} else if (val < tree->value) {
		tree->left = bstInsert(tree->left, val);
	} else if (val > tree->value) {
		tree->right = bstInsert(tree->right, val);
	}
	return tree;
}

static struct node *newNode(int val) {
	struct node *new = malloc(sizeof(struct node));
	if (new == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	new->value = val;
	new->left = NULL;
	new->right = NULL;
	return new;
}

/**
 * Returns true if the given value is in the BST, and false otherwise
 */
bool bstSearch(struct node *tree, int val) {
	if (tree == NULL) {
		return false;
	} else if (val < tree->value) {
		return bstSearch(tree->left, val);
	} else if (val > tree->value) {
		return bstSearch(tree->right, val);
	} else { // (val == tree->value)
		return true;
	}
}

/**
 * Deletes a value from the BST and returns the root of the updated BST
 */
struct node *bstDelete(struct node *tree, int val) {
	if (tree == NULL) {
		return tree;
	} else if (val < tree->value) {
		tree->left = bstDelete(tree->left, val);
	} else if (val > tree->value) {
		tree->right = bstDelete(tree->right, val);
	} else {
		struct node *new;
		if (tree->left == NULL) {
			new = tree->right;
		} else if (tree->right == NULL) {
			new = tree->left;
		} else {
			new = bstJoin(tree->left, tree->right);
		}
		
		free(tree);
		tree = new;
	}

	return tree;
}

static struct node *bstJoin(struct node *t1, struct node *t2) {
	if (t1 == NULL) {
		return t2;
	}
	if (t2 == NULL) {
		return t1;
	}

	struct node *curr = t2;
	struct node *parent = NULL;
	while (curr->left != NULL) {
		parent = curr;
		curr = curr->left;
	}

	if (parent != NULL) {
		parent->left = curr->right;
		curr->right = t2;
	}

	curr->left = t1;
	return curr;
}

/**
 * Prints the pre-order traversal of the BST
 */
void bstPreOrder(struct node *tree) {
	if (tree == NULL) return;

	showBstNode(tree);
	bstPreOrder(tree->left);
	bstPreOrder(tree->right);
}

/**
 * Prints the in-order traversal of the BST
 */
void bstInOrder(struct node *tree) {
	if (tree == NULL) return;

	bstInOrder(tree->left);
	showBstNode(tree);
	bstInOrder(tree->right);
}

/**
 * Prints the post-order traversal of the BST
 */
void bstPostOrder(struct node *tree) {
	if (tree == NULL) return;

	bstPostOrder(tree->left);
	bstPostOrder(tree->right);
	showBstNode(tree);
}

static void showBstNode(struct node *tree) {
	if (tree == NULL) return;
	printf("%d ", tree->value);
}

AVL Trees

avlInsert(t, v):
	Input:  AVL tree t, item v
	Output: t with v inserted

	if t is empty:
		return new node containing v
	else if v < t->item:
		t->left = avlInsert(t->left, v)
	else if v > t->item:
		t->right = avlInsert(t->right, v)
	else:
		return t

	return avlRebalance(t)

avlRebalance(t):
	Input:  possibly unbalanced tree t
	Output: balanced t

	bal = balance(t)
	if bal > 1:
		if balance(t->left) < 0:
			t->left = rotateLeft(t->left)
		t = rotateRight(t)
	else if bal < -1:
		if balance(t->right) > 0:
			t->right = rotateRight(t->right)
		t = rotateLeft(t)

	return t

balance(t):
	Input:  tree t
	Output: balance factor of t

	return height(t->left) - height(t->right)

avlDelete(t, v):
	Input:  AVL tree t, item v
	Output: t with v deleted

	if t is empty:
		return empty tree
	else if v < t->item:
		t->left = avlDelete(t->left, v)
	else if v > t->item:
		t->right = avlDelete(t->right, v)
	else:
		if t->left is empty:
			temp = t->right
			free(t)
			return temp
		else if t->right is empty:
			temp = t->left
			free(t)
			return temp
		else:
			successor = minimum value in t->right
			t->item = successor
			t->right = avlDelete(t->right, successor)

	return avlRebalance(t)

Graphs

Interface

typedef struct graph *Graph;

typedef int Vertex;

/**
 * Returns a new graph with nV vertices
 */
Graph GraphNew(int nV);

/**
 * Frees all memory allocated to the graph
 */
void GraphFree(Graph g);

/**
 * Returns the number of vertices in the graph
 */
int GraphNumVertices(Graph g);

/**
 * Returns the number of edges in the graph
 */
int GraphNumEdges(Graph g);

/**
 * Returns true if there is an edge between v and w,
 * and false otherwise
 */
bool GraphIsAdjacent(Graph g, Vertex v, Vertex w);

/**
 * Adds an edge between v and w
 */
void GraphInsertEdge(Graph g, Vertex v, Vertex w);

/**
 * Removes an edge between v and w
 */
void GraphRemoveEdge(Graph g, Vertex v, Vertex w);

/**
 * Displays the graph
 */
void GraphShow(Graph g);

Adjacency Matrix Implementation

struct graph {
	int nV;
	int nE;
	bool **edges;
};

static bool validVertex(Graph g, Vertex v);

Graph GraphNew(int nV) {
	Graph g = malloc(sizeof(struct graph));
	if (g == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	g->nV = nV;
	g->nE = 0;

	g->edges = malloc(nV * sizeof(bool *));
	for (int i = 0; i < g->nV; i++) {
		g->edges[i] = calloc(nV, sizeof(bool));
	}

	return g;
}

void GraphFree(Graph g) {
	for (int i = 0; i < g->nV; i++) {
		free(g->edges[i]);
	}
	free(g->edges);
	free(g);
}

int GraphNumVertices(Graph g) {
	return g->nV;
}

int GraphNumEdges(Graph g) {
	return g->nE;
}

bool GraphIsAdjacent(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	return g->edges[v][w];
}

void GraphInsertEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (g->edges[v][w]) {
		return;
	}
	
	g->edges[v][w] = true;
	g->edges[w][v] = true;
	g->nE++;
}

void GraphRemoveEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (!g->edges[v][w]) {
		return;
	}

	g->edges[v][w] = false;
	g->edges[w][v] = false;
	g->nE--;
}

void GraphShow(Graph g) {
	printf("Number of vertices: %d\n", g->nV);
	printf("Number of edges: %d\n", g->nE);
	printf("Edges:\n");
	for (int i = 0; i < g->nV; i++) {
		printf("%2d:", i);
		for (int j = 0; j < g->nV; j++) {
			if (g->edges[i][j]) {
				printf(" %d", j);
			}
		}
		printf("\n");
	}
	printf("\n");
}

static bool validVertex(Graph g, Vertex v) {
	return (v >= 0 && v < g->nV);
}

Adjacency List Implementation

struct graph {
	int nV;
	int nE;
	struct adjNode **edges;
};

struct adjNode {
	Vertex v;
	struct adjNode *next;
};

struct adjNode *adjListInsert(struct adjNode *l, int v);
struct adjNode *adjListDelete(struct adjNode *l, int v);
static bool validVertex(Graph g, Vertex v);

Graph GraphNew(int nV) {
	Graph g = malloc(sizeof(struct graph));
	g->edges = calloc(nV, sizeof(struct adjNode *));
	g->nV = nV;
	g->nE = 0;
	return g;
}

void GraphFree(Graph g) {
	for (int i = 0; i < g->nV; i++) {
		struct adjNode *curr = g->edges[i];
		while (curr != NULL) {
			struct adjNode *temp = curr;
			curr = curr->next;
			free(temp);
		}
	}
	free(g->edges);
	free(g);
}

int GraphNumVertices(Graph g) {
	return g->nV;
}

int GraphNumEdges(Graph g) {
	return g->nE;
}

bool GraphIsAdjacent(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL && w >= curr->v; curr = curr->next) {
		if (curr->v == w) {
			return true;
		}
	}
	return false;
}

void GraphInsertEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (!GraphIsAdjacent(g, v, w)) {
		g->edges[v] = adjListInsert(g->edges[v], w);
		g->edges[w] = adjListInsert(g->edges[w], v);
		g->nE++;
	}
}

static struct adjNode *adjListInsert(struct adjNode *l, int v) {
    if (l == NULL || v < l->v) {
        struct adjNode *new = newAdjNode(v);
        new->next = l;
        return new;
    } else if (v == l->v) {
        return l;
    } else {
        l->next = adjListInsert(l->next, v);
        return l;
    }
}

static struct adjNode *newAdjNode(int v) {
    struct adjNode *n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }
    n->v = v;
    n->next = NULL;
    return n;
}

void GraphRemoveEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (GraphIsAdjacent(g, v, w)) {
		g->edges[v] = adjListDelete(g->edges[v], w);
		g->edges[w] = adjListDelete(g->edges[w], v);
		g->nE++;
	}
}

static struct adjNode *adjListDelete(struct adjNode *l, int v) {
    if (l == NULL || v < l->v) {
        return l;
    } else if (v == l->v) {
        struct adjNode *newHead = l->next;
        free(l);
        return newHead;
    } else {
        l->next = adjListDelete(l->next, v);
        return l;
    }
}

void GraphShow(Graph g) {
	printf("Number of vertices: %d\n", g->nV);
	printf("Number of edges: %d\n", g->nE);
	printf("Edges:\n");
	for (int i = 0; i < g->nV; i++) {
		printf("%2d:", i);
		for (struct adjNode *curr = g->edges[i]; curr != NULL; curr = curr->next) {
			printf(" %d", curr->v);
		}
		printf("\n");
	}
	printf("\n");
}

static bool validVertex(Graph g, Vertex v) {
	return (v >= 0 && v < g->nV);
}

Array of Edges Implementation

#define DEFAULT_CAPACITY 16

struct graph {
	int nV;
	int nE;
	struct edge *edges;
	int maxE;
};

struct edge {
	Vertex v;
	Vertex w;
};

static bool validVertex(Graph g, Vertex v);

Graph GraphNew(int nV) {
	Graph g = malloc(sizeof(struct graph));
	g->nV = nV;
	g->nE = 0;

	g->edges = malloc(DEFAULT_CAPACITY * sizeof(struct edge));
	g->maxE = DEFAULT_CAPACITY;
	return g;
}

void GraphFree(Graph g) {
	free(g->edges);
	free(g);
}

int GraphNumVertices(Graph g) {
	return g->nV;
}

int GraphNumEdges(Graph g) {
	return g->nE;
}

bool GraphIsAdjacent(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	for (int i = 0; i < g->nE; i++) {
		if ((g->edges[i].v == v && g->edges[i].w == w) ||
				(g->edges[i].v == w && g->edges[i].w == v)) {
			return true;
		}
	}
	return false;
}

void GraphInsertEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	if (!GraphIsAdjacent(g, v, w)) {
		if (g->nE == g->maxE) {
			g->maxE *= 2;
			g->edges = realloc(g->edges, g->maxE * sizeof(struct edge));
		}
		g->edges[g->nE] = (struct edge){v, w};
		g->nE++;
	}
}

void GraphRemoveEdge(Graph g, Vertex v, Vertex w) {
	assert(validVertex(g, v));
	assert(validVertex(g, w));

	for (int i = 0; i < g->nE; i++) {
		if ((g->edges[i].v == v && g->edges[i].w == w) ||
				(g->edges[i].v == w && g->edges[i].w == v)) {
			g->edges[i] = g->edges[g->nE - 1];
			g->nE--;
			return;
		}
	}
}

void GraphShow(Graph g) {
	printf("Number of vertices: %d\n", g->nV);
	printf("Number of edges: %d\n", g->nE);
	printf("Edges:\n");
	for (int i = 0; i < g->nE; i++) {
		printf("(%d, %d)\n", g->edges[i].v, g->edges[i].w);
	}
	printf("\n");
}

static bool validVertex(Graph g, Vertex v) {
	return (v >= 0 && v < g->nV);
}

Breadth-First Search (BFS)

void bfs(Graph g, Vertex src) {
	int *predecessor = malloc(g->nV * sizeof(int));
	Queue q = QueueNew();

	for (int i = 0; i < g->nV; i++) {
		predecessor[i] = -1;
	}

	predecessor[src] = src;
	QueueEnqueue(q, src);

	while (QueueSize(q) > 0) {
		Vertex v = QueueDequeue(q);

		struct adjNode *curr = g->edges[v];
		for (; curr != NULL; curr = curr->next) {
			Vertex w = curr->v;

			if (predecessor[w] == -1) {
				predecessor[w] = v;
				QueueEnqueue(q, w);
			}
		}
	}

	free(predecessor);
	QueueFree(q);
}

Depth-First Search (DFS)

void dfs(Graph g, Vertex src) {
	bool *visited = calloc(g->nV, sizeof(bool));
	dfsRec(g, src, visited);
	free(visited);
}

static void dfsRec(Graph g, Vertex v, bool *visited) {
	visited[v] = true;

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL; curr = curr->next) {
		Vertex w = curr->v;
		if (!visited[w]) {
			dfsRec(g, w, visited);
		}
	}
}

Warshall's Algorithm

warshall(A):
	Input: n x n adjacency matrix A
	Output: n x n reachability matrix

	create tc matrix which is a copy of A

	for each vertex k in G: // from 0 to n - 1
		for each vertex s in G:
			for each vertex t in G:
				if tc[s][k] and tc[k][t]:
					tc[s][t] = true

	return tc

Dijkstra's Algorithm

dijkstraSSSP(G, src):
	Input: graph G, source vertex src

	create dist array, initialised to inf
	create pred array, initialised to -1
	create vSet containing all vertices of G

	dist[src] = 0
	while vSet is not empty:
		find vertex v in vSet such that dist[v] is minimal
		remove v from vSet
		for each edge (v, w, weight) in G:
			if dist[v] + weight < dist[w]:
				dist[w] = dist[v] + weight
				pred[w] = v

Kruskal's Algorithm

kruskalMst(G):
	Input:  graph G with V vertices
	Output: minimum spanning tree of G

	mst = empty graph with V vertices
	sortedEdges = sort edges of G by weight
	for each edge (v, w, weight) in sortedEdges:
		if there is no path between v and w in mst:
			add edge (v, w, weight) to mst
		if mst has V - 1 edges:
			return mst

	no mst

Prim's Algorithm

primMst(G):
	Input:  graph G with V vertices
	Output: minimum spanning tree of G

	mst = empty graph with V vertices
	usedV = {0}
	unusedE = edges of G
	while |usedV| < V :
		find cheapest edge e (s, t, weight) in unusedE such that
				s in usedV and t not in usedV

		add e to mst
		add t to usedV
		remove e from unusedE

	return mst

Hash Tables

Interface

typedef struct hashTable *HashTable;

/**
 * Creates a new empty hash table
 */
HashTable HashTableNew(void);

/**
 * Frees all memory allocated to the hash table
 */
void HashTableFree(HashTable ht);

/**
 * Inserts a key-value pair into the hash table. If the key already
 * exists, the existing value is replaced with the given value.
 */
void HashTableInsert(HashTable ht, int key, int value);

/**
 * Deletes a key-value pair from the hash table, if it exists
 */
void HashTableDelete(HashTable ht, int key);

/**
 * Returns true if the hash table contains the given key, and false
 * otherwise
 */
bool HashTableContains(HashTable ht, int key);

/**
 * Returns the value associated with the given key in the hash table.
 * Assumes that the key exists.
 */
int HashTableGet(HashTable ht, int key);

/**
 * Returns the number of key-value pairs in the hash table
 */
int HashTableSize(HashTable ht);

Separate Chaining Implementation

#define INITIAL_NUM_SLOTS 11

#define MAX_LOAD_FACTOR 2.0

struct hashTable {
	struct node **slots;
	int numSlots;
	int numItems;
};

struct node {
	int key;
	int value;
	struct node *next;
};

static void freeList(struct node *list);
static struct node *doInsert(HashTable ht, struct node *list,
                             int key, int value);
static struct node *newNode(int key, int value);
static struct node *doDelete(HashTable ht, struct node *list, int key);
static inline unsigned int hash(int key, int N);

HashTable HashTableNew(void) {
	HashTable ht = malloc(sizeof(*ht));
	if (ht == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	ht->slots = calloc(INITIAL_NUM_SLOTS, sizeof(struct node *));
	ht->numSlots = INITIAL_NUM_SLOTS;
	ht->numItems = 0;

	return ht;
}

void HashTableFree(HashTable ht) {
	for (int i = 0; i < ht->numSlots; i++) {
		freeList(ht->slots[i]);
	}
	free(ht->slots);
	free(ht);
}

static void freeList(struct node *list) {
	struct node *curr = list;
	while (curr != NULL) {
		struct node *temp = curr;
		curr = curr->next;
		free(temp);
	}
}

void HashTableInsert(HashTable ht, int key, int value) {
	if (ht->numItems >= MAX_LOAD_FACTOR * ht->numSlots) {
		printf("warning: resize not implemented!\n");
	}

	int i = hash(key, ht->numSlots);
	ht->slots[i] = doInsert(ht, ht->slots[i], key, value);
}

static struct node *doInsert(HashTable ht, struct node *list,
                             int key, int value) {
	if (list == NULL) {
		ht->numItems++;
		return newNode(key, value);
	} else if (list->key == key) {
		list->value = value;
		return list;
	} else {
		list->next = doInsert(ht, list->next, key, value);
		return list;
	}
}

static struct node *newNode(int key, int value) {
	struct node *new = malloc(sizeof(struct node));
	if (new == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	new->key = key;
	new->value = value;
	new->next = NULL;
	return new;
}

void HashTableDelete(HashTable ht, int key) {
	int i = hash(key, ht->numSlots);
	ht->slots[i] = doDelete(ht, ht->slots[i], key);
}

static struct node *doDelete(HashTable ht, struct node *list, int key) {
	if (list == NULL) {
		return NULL;
	} else if (list->key == key) {
		ht->numItems--;
		struct node *newHead = list->next;
		free(list);
		return newHead;
	} else {
		list->next = doDelete(ht, list->next, key);
		return list;
	}
}

bool HashTableContains(HashTable ht, int key) {
	int i = hash(key, ht->numSlots);
	struct node *curr;
	for (curr = ht->slots[i]; curr != NULL; curr = curr->next) {
		if (curr->key == key) {
			return true;
		}
	}
	return false;
}

int HashTableGet(HashTable ht, int key) {
	int i = hash(key, ht->numSlots);
	struct node *curr;
	for (curr = ht->slots[i]; curr != NULL; curr = curr->next) {
		if (curr->key == key) {
			return curr->value;
		}
	}
	
	printf("error: key %d does not exist!\n", key);
	return -1;
}

int HashTableSize(HashTable ht) {
	return ht->numItems;
}

static inline unsigned int hash(int key, int N) {
	const unsigned int magic = 0x45d9f3b;
	unsigned int h = 1U + INT_MAX;
	h += key;
	h = ((h >> 16) ^ h) * magic;
	h = ((h >> 16) ^ h) * magic;
	h = (h >> 16) ^ h;
	return h % N;
}

Priority Queues

Interface

typedef struct pq *Pq;

/**
 * Creates a new empty priority queue
 */
Pq PqNew(void);

/**
 * Frees all memory allocated to the priority queue
 */
void PqFree(Pq pq);

/**
 * Inserts an item with the given priority into the priority queue
 */
void PqInsert(Pq pq, int item, int priority);

/**
 * Deletes the item with the highest priority from the priority queue
 * and returns it
 */
int PqDelete(Pq pq);

/**
 * Returns the item with the highest priority from the priority queue
 */
int PqPeek(Pq pq);

Binary Heap Implementation

#define INITIAL_CAPACITY 8

struct pq {
	struct pqItem *items;
	int numItems;
	int capacity;
};

struct pqItem {
	int item;
	int priority;
};

static void resize(Pq pq);
static void fixUp(struct pqItem *items, int i);
static void swap(struct pqItem *items, int i, int j);
static void fixDown(struct pqItem *items, int i, int N);

Pq PqNew(void) {
	Pq pq = malloc(sizeof(struct pq));
	if (pq == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	pq->numItems = 0;
	pq->capacity = INITIAL_CAPACITY;
	pq->items = malloc((pq->capacity + 1) * sizeof(struct pqItem));

	return pq;
}

void PqFree(Pq pq) {
	free(pq->items);
	free(pq);
}

void PqInsert(Pq pq, int item, int priority) {
	if (pq->numItems == pq->capacity) {
		resize(pq);
	}

	pq->numItems++;
	pq->items[pq->numItems] = (struct pqItem){
		.item = item,
		.priority = priority,
	};
	fixUp(pq->items, pq->numItems);
}

static void fixUp(struct pqItem *items, int i) {
	while (i > 1 && items[i].priority > items[i / 2].priority) {
		swap(items, i, i / 2);
		i = i / 2;
	}
}

static void swap(struct pqItem *items, int i, int j) {
	struct pqItem tmp = items[i];
	items[i] = items[j];
	items[j] = tmp;
}

static void resize(Pq pq) {
	pq->capacity *= 2;
	pq->items = realloc(pq->items, (pq->capacity + 1) * sizeof(struct pqItem));
	if (pq->items == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}
}

int PqDelete(Pq pq) {
	if (pq->numItems == 0) {
		fprintf(stderr, "error: pq is empty\n");
		exit(EXIT_FAILURE);
	}

	int item = pq->items[1].item;
	pq->items[1] = pq->items[pq->numItems];
	pq->numItems--;
	fixDown(pq->items, 1, pq->numItems);
	return item;
}

static void fixDown(struct pqItem *items, int i, int N) {
	while (2 * i <= N) {
		int j = 2 * i;
		if (j < N && items[j + 1].priority > items[j].priority) {
			j++;
		}
		if (items[i].priority >= items[j].priority) {
			break;
		}
		swap(items, i, j);
		i = j;
	}
}

int PqPeek(Pq pq) {
	if (pq->numItems == 0) {
		fprintf(stderr, "error: pq is empty\n");
		exit(EXIT_FAILURE);
	}

	return pq->items[1];
}

Tries

#define ALPHABET_SIZE 26

typedef struct node *Trie;

struct node {
	struct node *children[ALPHABET_SIZE];
	bool finish;
};

/**
 * Creates a new empty trie
 */
Trie trieNew(void) {
	Trie t = calloc(1, sizeof(*t));
	if (t == NULL) {
		fprintf(stderr, "error: out of memory\n");
		exit(EXIT_FAILURE);
	}

	return t;
}

/**
 * Frees all memory allocated to the trie
 */
void trieFree(Trie t) {
	if (t == NULL) {
		return;
	}

	for (int i = 0; i < ALPHABET_SIZE; i++) {
		trieFree(t->children[i]);
	}
	free(t);
}

/**
 * Inserts a key into the trie
 * Returns the trie
 */
Trie trieInsert(Trie t, char *key) {
	if (t == NULL) {
		t = calloc(1, sizeof(*t));
	}

	if (key[0] == '\0') {
		t->finish = true;
		return t;
	}

	int i = key[0] - 'a';
	t->children[i] = trieInsert(t->children[i], &key[1]);
	return t;
}

/**
 * Returns true if the given key is in the trie, and false otherwise
 */
bool trieSearch(Trie t, char *key) {
	if (t == NULL) {
		return false;
	}

	if (key[0] == '\0') {
		return t->finish;
	}

	char first = key[0];
	int i = first - 'a';
	return trieSearch(t->children[i], &key[1]);
}

/**
 * Deletes a key from the trie if it exists
 * Returns the trie
 */
Trie trieDelete(Trie t, char *key) {
	if (t == NULL) {
		return t;
	} else if (key[0] == '\0') {
		t->finish = false;
	} else {
		int i = key[0] - 'a';
		t->children[i] = trieDelete(t->children[i], &key[1]);
	}

	if (t->finish) {
		return t;
	}

	for (int i = 0; i < ALPHABET_SIZE; i++) {
		if (t->children[i] != NULL) {
			return t;
		}
	}

	free(t);
	return NULL;
}