You take a photo on your iPhone X's 12MP camera; that's 12 million pixels! This is roughly 36 MB of data -- but it only takes about 1 MB of space on your computer. How were you able to store the entire image in 1/36 of its actual size?
The magic: compression algorithms!
We will be discussing various techniques for the compression of data, starting from the basics (RLE) and ranging to lossless methods such as entropy encoding, LZW compression, and the Burrows-Wheeler Transform.
The last part of the class will be an exploration of compression methods for images, taking a look at some ad hoc approaches that we might try (8-bit graphics!). We'll then conclude with an in-depth examination of how modern lossy algorithms, like JPEG, are able to achieve ~20x compression ratios with no perceptible change in quality.