Algorithms in Go

Data structures and algorithms implemented in Go.

Overview

This course requires you to implement a collection of common data structures and algorithms as Go packages. Your code is automatically tested for correctness (unit tests) and performance (CPU cycle measurement against a reference baseline).

There are 28 exercises worth a total of 123 points across 14 topics.

Getting Started

Sign in at classbox.dev with your GitHub account.
Enroll in the Algorithms in Go course. This installs a GitHub App on a repository created from the course template.
Clone the repository to your local machine.
Implement the exercises as Go packages following the descriptions below.
Commit and push your changes to trigger automatic grading.
Check your results on classbox.dev or in the GitHub Check Run on your commit.

Rules

Allowed packages

Your source code can only import the following standard library packages:

errors
fmt
sort
strings
strconv
math
math/rand
math/bits
container/heap
container/list

Imports between your own stdlib packages are also allowed.

Code style

All code must pass gofmt. Run gofmt -w -l . before committing to fix formatting issues.

Testing

Unit tests check correctness: return values, edge cases, memory constraints, and input immutability.

Performance tests measure CPU cycles on large inputs and compare to a reference baseline. Your code must reach 120% of the baseline or less to pass.

Test source code is not published. You are encouraged to write your own tests using Go's testing package.

Exercises

Introduction

Exercise	Description	Score
`cmp`	Min and Max functions for a variable number of arguments.	0
`primes`	NthPrime function for computing prime numbers.	3

Data Structures

Exercise	Description	Score
`vector`	Dynamic array with memory management. Uses constant-factor expansion (α=4/3) and shrinking strategy. Built-in append() is not permitted.	7
`matrix`	Two-dimensional row-major array. The row-major requirement is essential — otherwise the implementation will fail performance tests due to cache misses.	3
`ndarray`	Prototype of a row-major n-dimensional array. Computes linearised indices for given n-dimensional coordinates without holding the actual data.	3
`maxqueue`	FIFO queue with fast queries for the maximal element. Max() in guaranteed constant time, Push() and Pop() in amortised constant time.	3

Sorting and Selection

Exercise	Description	Score
`nthelement`	NthElement selection algorithm.	4
`firstn`	FirstN selection algorithm.	5
`radix`	Radix sort algorithm.	4
`listsort`	Sort algorithm for container/list linked lists.	5

Hashing

Exercise	Description	Score
`lru`	Fixed-size cache with Least Recently Used (LRU) replacement policy.	3

Trees

Exercise	Description	Score
`treebalanced`	Construct a balanced binary search tree.	3
`treeinorder`	Non-recursive in-order traversal of a binary tree. Must be implemented without recursion.	3
`treeserialise`	Encode and Decode functions for binary trees using level-order serialisation format.	4
`treesym`	Check if a binary tree is symmetric.	3
`treenoleft`	Transform a binary tree to have no left children.	3

Sets

Exercise	Description	Score
`bitset`	Fixed-size sequence of bits with an interface for setting and testing individual bits. Interface is a subset of std::bitset from C++.	5
`set`	Ordered collection of unique elements with logarithmic operations. Reference implementation uses skip-list with maximum 26 pointer levels. Supports iterator-based traversal with LowerBound/UpperBound.	10

Dynamic Programming

Exercise	Description	Score
`levenshtein`	Compute Levenshtein distance and edit transcripts between strings. Operations: Insert, Replace, Delete, Match.	5
`lcs`	Longest Common Subsequence algorithm.	4
`segmentation`	String segmentation using dynamic programming.	4

Graphs: Ancestry

Exercise	Description	Score
`treeancestry`	Fast ancestry enquiries in binary trees using depth-first search properties.	4

Graphs: Grid Problems

Exercise	Description	Score
`islands`	Count non-zero regions on an integer grid. Grid mutation is allowed, no graph package required.	4

Graphs: Data Structure

Exercise	Description	Score
`graph`	Data structure for directed or undirected graphs using adjacency list representation.	5

Graphs: Topological Sort

Exercise	Description	Score
`tsort`	Topological sorting of directed graphs. Must be implemented non-recursively.	7

Graphs: Minimum Spanning Tree

Exercise	Description	Score
`mst`	Minimum spanning tree algorithm for undirected graphs.	7

Graphs: Shortest Paths

Exercise	Description	Score
`dijkstra`	Dijkstra’s shortest path algorithm.	7

Strings

Exercise	Description	Score
`fulltext`	Simple fulltext search: find documents containing all query words, order-independent. No specialised data structures required.	5