00. Preamble

What This Course Is Really Asking#

Suppose you have a million student records and want to find one student, keep the records ordered, or repeatedly select the next person to serve. All three tasks involve the same records, but they reward different representations. An unordered array is easy to append to; a sorted array permits binary search; a heap is designed to remove the most urgent item. Basically, the data structure changes which operations are cheap.

A data structure is a concrete organisation of stored data and the relationships between its parts. An algorithm is a finite, precise procedure for solving a problem. An abstract data type, or ADT, describes the operations and their meaning without fixing the storage. A set ADT, for example, promises membership, insertion and deletion; an array, a search tree and a hash table are competing implementations of that promise.

The course asks you to connect four things: what an operation means, how its representation implements it, why the algorithm is correct, and how its cost grows. Knowing the name “Dijkstra” is only the beginning. You should be able to trace its choices, state its weight assumption, reconstruct paths, and explain how the representation changes its running time.

Practice. Is “return the smallest stored key” a representation or an operation? Does it force us to use a sorted array?

How to Work Through These Notes#

Read in filename order on a first pass. C and Linked Lists prepares the pointer reasoning used by Recursion, trees and graph adjacency lists. Analysis of Algorithms supplies the language used throughout the course. Sorting develops loop invariants and divide and conquer before the ADTs, trees and graph chapters. Hashing, heaps and tries then give alternative solutions to problems you already understand.

Use this chapter map to return to a topic while revising. Each note also starts with a table of contents; in the site preview its section links appear beside the article, while Obsidian's TOC plugin can show the same heading structure in the vault.

For each algorithm, first trace a small example on paper. Write the state after each meaningful change: which pointer changed, which prefix is sorted, which vertex was discovered, or which bucket received the key. Next explain the rule that makes the next step safe. Finally implement it and test cases that exercise its assumptions. A correct-looking final answer does not establish that every intermediate step followed the algorithm.

Inline questions are part of the lesson. Attempt them before opening their answers. Checkpoints collect the ideas you should now be able to explain. The final revision chapter mixes topics so you practise choosing an approach instead of being told which algorithm to use.

Static figures and prose remain usable in Obsidian. The site's algorithm fences add a step player; their recorded counters describe particular traces, not exhaustive CPU instructions or wall-clock timing. If Obsidian displays a fence as text, use the adjacent worked example or the local site preview.

Tools: Compile, Observe, Diagnose#

The introduction deck moves from dcc to Clang and explicit debugging tools. A useful baseline on a machine with Clang is:

clang -std=c11 -Wall -Wextra -Werror -g program.c -o program
./program

-std=c11 chooses the language version; warning flags expose suspicious code; -g retains information useful to a debugger. Fix a warning by understanding it, not by removing the warning flag. A compiler accepts syntax and types; it cannot prove your linked-list ownership or graph invariant.

Sanitizers and Valgrind#

Undefined behaviour means that the C language gives no required meaning to an operation, such as dereferencing freed memory or overflowing a signed integer. A sanitizer adds checks to an executable. Different tools observe different faults:

For example, an AddressSanitizer build commonly uses:

clang -std=c11 -Wall -Wextra -g -fsanitize=address,undefined program.c -o program
./program

Do not combine every sanitizer indiscriminately: MemorySanitizer and AddressSanitizer require separate builds. Availability depends on the machine and runtime. A clean run only covers executed paths; it does not establish that an untested branch is correct. If you free a node and then read node->next, the fault is the lifetime of the node, even if one ordinary run happens to print the right result.

Practice. A program produces the correct numbers but LeakSanitizer reports a lost allocation. Is the algorithm fully implemented correctly?

Makefiles#

make rebuilds targets whose prerequisites have changed. A small example is:

CC = clang
CFLAGS = -std=c11 -Wall -Wextra -Werror -g

program: main.o List.o
	$(CC) $(CFLAGS) main.o List.o -o program

main.o: main.c List.h
List.o: List.c List.h

.PHONY: clean
clean:
	rm -f program main.o List.o

Recipe lines begin with a real tab. The List.h dependency matters: changing a declaration can require recompiling both source files, even if neither .c file changed. clean is a named action rather than an output file, so .PHONY prevents a file named clean from hiding it.

Notation and Conventions#

Unless a chapter says otherwise, arrays use zero-based indices, integer keys are compared in ascending order, and constant-time primitive operations use fixed-width machine values. n counts stored items; a graph uses V for its number of vertices and E for its number of edges; h describes a tree's height with the chapter's stated convention. String algorithms also need the key length: hashing a long string is not constant-time just because the table lookup uses few probes.

Auxiliary space is temporary working memory beyond the input representation and required output. Recursive call frames count. A structure storing n items uses storage even when one operation takes constant auxiliary space. Best, worst, expected and amortised costs answer different questions; the analysis chapter derives them.

The downloaded 26T1 slides are the content authority. These notes retain the lecture variants and explain corrections where slide pseudocode has a typo or an abbreviated claim. Administrative slides record arrangements for that term; they are not a current timetable or assessment-policy reference. The technical revision material is included, while promotional slides, feedback QR codes and staff introductions do not need textbook chapters.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. A sanitizer reports a heap-use-after-free in printList after deleteHead returns. What two source-level facts would you check before changing printList?

Question 2. A program passes its example test but fails the hidden empty-list case. What small test matrix would expose the likely boundary bugs?