Computer Science

If you were to invent computer science from scratch, how would I do it? We can divide them into three chronological pillars. First is the theory of algorithms. Second is the construction of computers. Third is the applications of algorithms.

The design and analysis of algorithms are much older than computers in general, having existed as early as 2000 BC when Egyptians developed methods to multiply two numbers (even more primitive cookbooks can be considered algorithms). But in order to do any algorithm, we need a way to store data, whether it's through writing in a piece of paper or storing in computer memory. This requires the use of data structures which, coupled with algorithms, can solve whatever problems that came up in our lives. Note that none of these data structures or algorithms require the use of a computer at all. Graphs could be drawn on a piece of paper, a stack of accounting bills on your desk is literally the stack data structure, and a long list of names and ages of citizens in a tablet can be considered an array (erasing someone off from a tablet would leave an empty space). These different forms of bookkeeping, through different data structures, have advantages and disadvantages.

When mechanical computers were invented in 1822 followed by the first electronic comptuers in 1943, we could rapidly scale these algorithms. Computing prime numbers did not have to be done by hand, and all the theory developed before then can be applied much more widely. But if you look at all the components in your computer, it's baffling to wonder how humanity could create such a complex and intricate object. I mean, certain smartphones that fit into your pocket is able to store the equivalent of 8 trillion on-off switches! This is why the next pillar deals with the construction of computers, which starts off with the most basic component: a transitor. This requires computer engineering and physics knowledge, but from here we slowly build upon abstractions to instruction sets and CPU design. The instruction set of a CPU is strongly tied to the architecture of a computer, and so we must introduce the Assembly language as a way to interact with the computer. Once we introduce the concept of memory (e.g. how different data types are stored), input/output devices, and databuses, this completes the von Neumann architecture of a computer. Finally, we talk about the rest of the computer, such as disks (how data persists even after the computer is turned off), GPUs, etc. Once we are finished with the computer engineering part, we now know how a computer is built. Finally, we talk about some low-level programs such as the firmware that is required to run before a computer turns on.

We have successfully built a computer, but we are not out of the construction pillar just yet. Just because we have a functional computer, it doesn't mean that it is very user-friendly. Therefore, an abstraction over the different architectures is the C programming language (plus C++ since I use it frequently). But to work with languages at all, we must need some way to turn the human-friendly language into machine code that the computer can process. This is the job of compilers, which constitutes another set of notes. Furthermore, computers are not monolithic objects that can operate one task at a time. There is a need to control multiple programs/processes and execute them concurrently, which is the job of the operating system (OS) and opens up a whole new can of worms on how to manage these processes (e.g. virtual memory, mutex locks, etc.). Note that the OS is simply another process, and in order to start the OS, the previously mentioned firmware must activate a bootloader that finds the correct operating system, and so bootloaders such as GRUB will be talked about here. Once the OS has started, this is a natural point to introduce shells (terminals) as a way to interact with the computer through the OS. Finally, we can introduce virtualization software like virtual machines (VMs) and containers (e.g. Docker) which isolate different processes as if they were running with their own operating system.

Great, now that we know how algorithms work and how to run them on computers, we can focus on the application of algorithms, our third pillar. I introduce the two most common languages in the world, Python and JavaScript, which are much higher level and used the most often when developing software or doing research. A powerful feature of the computer is the ability to connect to the world wide web, but to understand this we need to know how computers talk to each other, i.e. computer networking. On a closely related note, networking now allows multiple computers to work on one task, which is the topic of distributed systems. With the explosion of computing power and networks all over the world, the need for databases to store this exponentially growing data also motivates its own area of study.

On an individual level, there are several meta-programming tools that a developer runs into when working with code. First, you need a text editor, and I give a quick guide on NeoVim which is my go-to. Second, you need good version control, which is a systematic way to update code when working in a team, and git is universally used for this. Good version control almost always comes with automated processes and tests (usually run on Docker containers), known as continuous integration/development (CI/CD). You will see all of these concepts in (mostly) industry and (less in) research.

Finally I end with some miscellaneous applications such as blockchain and SLAM.

All of my personal notes are free to download, use, and distrbute under the Creative Commons "Attribution- NonCommercial-ShareAlike 4.0 International" license. Please contact me if you find any errors in my notes or have any further questions.