This video is part of my lecture course on Algorithms at the University of Cambridge.
To understand data structures, we take the microprocessor’s viewpoint: memory is merely a collection of bytes, and it’s up to us to give meaning to those bytes. We use the historic Sinclair ZX Spectrum, made in Cambridge in 1982, to illustrate. The same byte may be a number between 0 and 255, or a part of a larger number, or a bitmap, or a sound sample, or an ASCII character, or a machine code instruction, and so forth. The primitive data types the processor understands would typically include integers (signed or unsigned), arguably booleans and characters (perhaps), nowadays floats (but not so in the early 1980s) and not very much else. To form more complex data structures you combine simpler ones with arrays, records and pointers.
Pointers are a fundamental concept in computing. Extremely simple (a pointer is just a fancy name for a memory address), extremely powerful (almost every non-trivial data structure involves pointers) and they are the potential source of spectacular bugs. One of the principal preoccupations of high level languages is to reduce the likelihood that you’ll shoot your foot off by misusing pointers. We explain how linked data structures are constructed out of records and pointers and we demonstrate some of the most basic pitfalls of low level pointer access.
Many thanks to those of you who are giving thumbs up to these videos and subscribing to the channel. Your support is greatly appreciated and it causes Youtube to offer this material to more viewers who might like it.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/
Course handout:
https://www.cl.cam.ac.uk/teaching/2021/Algorithms/2020-2021-stajano-algs-handout.pdf
My home page:
https://frank.stajano.com
Add comment