[TOC]
Over the past several decades, computer science (CS) gradually established itself as an enabler of modern society. It is the “T” in STEM, standing for “technology” or “trouble”, depending on perspective. Today’s cutting-edge innovations in CS are powered by the computing hardware of the 2020s. The programming languages and software techniques that now run the technology sector were sired by CS in the 1990s. Its prominance notwithstanding, though, CS is a very young field, having matured into an independent discipline only in the 1960s. It was born relatively recently, in the 1930s, as a subfield of mathematics. And when society transitions to quantum computing in the not-so-distant future, CS will incorporate physics of the 1900s.
But despite the name “computer science”, it is not a branch of natural science and it is not especially concerned with computer hardware. Dijkstra, the famous Dutch computer scientist, once said, “Computer science is no more about computers than astronomy is about telescopes.” The name “computer science”, perhaps, was a poor choice for the field. Indeed, the title “computer scientist” does not describe the calling as accurately as the labels “shoemaker” and “gravedigger” do those vocations.
In many respects, computer science is very like applied physics, electrical engineering, and applied mathematics. In all these fields, mathematics is used to analyse problems methodically and derive solutions systematically. Problems that computer technology solves range far and wide into science, engineering, and mathematics. For example, it performs mundane tasks like experiment record keeping and scientific equipment monitoring. It animates life-critical engineering systems like air traffic control and medical devices. It tackles sublime mathematical matters like automated theorem proving and artificial intelligence. In turn, growth and maturity of technology is driven by advancements made in mathematics, science, and engineering.
In spite of the close relationship CS has with its STEM siblings, however, the most visible application of technology today is in business computing. And a common misconception is that CS is just coding. Coding is surely part of CS, but it is not the main focus of CS. One who wishes to become a coder does not need to study CS for years on end; he could study on his own to learn a popular programming language, say JavaScript or Python, and enter the trade as a junior developer, immediately. In stark contrast, a youngster aspiring to become a computer scientist must be prepared for a career-long pursuit of knowledge, skills, and self-improvement.
In this article, I describe the CS curriculum at a high level. The target audience are counsellors and parents of a high-schooler who is contemplating a career as a computer scientist (but not just a coder). Here, I make the following, self-evident assumptions:
There are differences between men and women, but intellect, aptitude, and zeal are not among them. Like all human endeavours, STEM, too, has many high-achieving women. The world’s first programmer was Lady Ada Lovelace (1815 - 1852), an English mathematician and the collaborator of another famous English mathematician, Babbage, who designed the Analytical Engine, the world’s first programmable, general-purpose computer. Emmy Noether (1882 - 1935) was a German mathematician who made numerous, important contributions to abstract algebra and physics. COBOL, a pioneering, high-level programming language and the first, successful business programming language, was based on FLOW-MATIC language. The designer of FLOW-MATIC was American computer scientist Admiral Grace Hopper (1906 - 1992). Mathematician Katherine Johnson (1918 - 2020) was the first African-American woman to work at NASA as a scientist. In her four-decade-long career at NASA, she worked on orbital mechanics for Mercury, Apollo, Shuttle, and Mars missions. American computer scientist Frances Allen (1932 - 2020) was the first female IBM Fellow and, more importantly, the first female winner of the Turing Award. This award is the most prestigious one in computing. She received it for her seminal work in optimising compilers. Sophie Wilson, born Roger Wilson (1957), is the English computer scientist who designed the instruction set architecture of the ARM microprocessor. Her creation went on to conquer the world of CPUs, and today it powers practically all mobile phones, tablet computers, and embedded devices.
It is undeniable that STEM fields, including IT, discriminate against women—just look at the pay gap, nay pay gash. It is the duty of all STEMers to recognise gender discrimination, both institutionalised and individualised varieties, and do our utmost to remedy that disparity.
Now comes the rub. Unlike many other languages, English has no gender-neutral pronoun and possesive. As such, I follow the grammatical convention of using “he” and “his”, when referring to a generic person. I strive to minimise the use of masculine words as generics, but not at the cost of flow and clarity.
Before we explore the CS curriculum, we shall first examine non-CS fields whose specialities overlap with computing.
While there are overlaps between CS and the above-mentioned fields, as well as amongst themselves, each field takes a unique approach to the subjects. For instance, mathematicians study category theory because it is part of the foundation of mathematics, but computer scientists use the language of category theory to talk about type theory and functional programming concepts in clear, concise ways. Similarly, electrical engineers study how microprocessors are designed and fabricated, but computer scientists study how microprocessors perform computations. And data scientists write small programmes that manipulate, organise, and analyse data, but computer scientists focus on designing efficient algorithms that manipulate, organise, and analyse data on massive scales.
Note that there is a clear distinction between someone who writes programmes and someone who designs algorithms. Applied mathematicians, engineers, scientists, economists, business analysts, and web developers write programmes. Their focus is on getting the job done. But computer scientists, in addition to writing efficient programmes, are concerned with the design of algorithms, namely the mathematical expressions of algorithm performance and mathematical proofs of algorithm correctness. Salient facts are these:
The CS curriculum is expansive, but the tie that binds all specialities within this field is mathematics. In its purest form, CS is a mathematical problem solving discipline. As such, the theoretical curriculum covers many branches of mathematics, including at a minimum discrete structures, mathematical logic, combinatorics, probability theory, computability theory, complexity theory, and algorithm analysis. On the more practical side, the curriculum includes programming languages, computer organisation, operating systems, communication networks, and database management systems as core requirements.
The first half of the CS curriculum introduces the prerequisites: discrete structures, computer organisation, introduction to programming, and algorithms. The second half teaches more advanced core courses and the electives in various specialities. Theoretical electives comprise in-depth courses in category theory, formal languages, computability theory, complexity theory, type theory, compiler theory, numerical analysis, information theory, natural language processing, and other mathematics-oriented courses. Practical electives include parallel computing, distributed computing, distributed file systems, computer architecture, embedded systems, computer graphics, digital image processing, digital signal processing, machine learning, data science, big data, robotics, game design, and countless others. A few of these practical courses are perennial, but most are ephemeral, surging in, then washing out, with the rhythmic tide of industrial trends.
Since even the practical courses need good amounts of theory, it is better to think of the CS curricula as a continuum of mathematics-oriented courses with the core courses leaning heavily toward mathematics; others a mix of mathematics, computing, and engineering; and the rest less mathematical more practice oriented. These divisions give rise to the major subfields within CS: theoretical computer science, computer engineering, and computing systems. Roughly speaking, theoretical computer science is academia focused, computer engineering is industry focused, and computing systems is business focused.
CS curricula from various institutions differ in emphasis. Universities with strong engineering traditions—there are but a handful of them in the world—offer computer engineering (CE), which is a mix of electrical engineering and computer science. Graduates from these top engineering colleges usually join giant technology firms, the best among them becoming famous CPU designers. Universities with strong mathematical traditions—equally exclusive and few in numbers—lean toward theoretical computer science. The best of their graduates typically remain in academia and expand the boundaries of CS by becoming professors at top universities around the world. The rest—the vast majority of lesser institutions—shape their curricula to fit the perpetually shifting trends of the IT industry. This industry-centric approach is instantly profitable for both the universities and their graduates. But it has a substantial, latent cost: this approach tends to produce graduates who are proficient practitioners in one speciality but possess less-than-adequate theoretical sophistication.
Although not a requirement, it is highly recommended that CS students take a few introductory courses from electrical engineering, applied physics, applied mathematics, mathematical economics, and philosophy; elementary, theoretical knowledge of those fields will broaden their perspective. On the flip side, a graduate with a pure mathematics degree from a top university can learn on his own the theoretical side of CS. Similarly, a graduate with a degree in electrical engineering, applied physics, or applied mathematics from a top university can learn on his own the practical side of CS. To put it another way, a mathematically mature baccalaureate with a degree in engineering, physics, mathematics, or economics can study graduate-level CS topics, either on his own or in graduate school, if he is prepared to fill the few gaps in his knowledge, on his own.
Given the breadth of the CS field, it is impossible for a curriculum to cover all the application domains. The good news, though, is that a CS graduate with a firm theoretical foundation and basic practical skills can learn on his own any advanced practical skill, when the need arises. But the converse is not true: experience and skills in one practical speciality, no matter how extensive, do not translate to another speciality, without the knowledge of the foundational theories of both specialities. It is a known fact that the risk of a premature specialisation is a stunted intellectual maturity, which is a career-long debility. Therefore, it is emphatically the province and duty of the CS student to acquire the essential theoretical knowledge first, before knocking about in advanced, practical electives.
All STEM students are required to take elementary courses in mathematics: calculus, linear algebra, statistics, and proof techniques. Advanced students would have studied some or all of these subjects in high school AP courses. Beyond these mathematical rudiments are the theoretical foundation of CS, which comprises the following branches of mathematics: discrete structures, mathematical logic, combinatorics, probability theory, automata theory, compiler theory, and numerical analysis.
discrete structures—Discrete structures is an introductory course in discrete mathematics, the branch of mathematics that studies mathematical objects that are discrete (countable) like integers and graphs. The study of integers and integer-valued functions is called number theory, and its most famous application is cryptography. Graph theory studies the dynamism of networked objects. It has applications not only throughout CS but also in mathematics, engineering, physics, chemistry, biology, linguistics, and social science. The public knows the graph, well: the Web is a graph; a social media friends network is a graph.
mathematical logic—Mathematical logic studies sets, logic, and proofs. Nearly all of modern mathematics is founded upon set theory. Set theory is informally (intuitively) introduced in high school, and a college-level course presents sets and functions formally (abstractly), which prepares the student for the study of formal logic. Logic is at the heart of theoretical CS. Indeed, the very notion of computation is defined by mathematical logic. A course in logic teaches logic operations, inferences, and proof techniques. Proofs propel mathematics. But they have practical applications in CS, where tradition demands that programmers provide mathematical proofs of correctness and efficiency of the algorithms they designed. And it turns out that there is a one-to-one correspondence between types and propositions as well as between programmes and proofs, known as Curry-Howard isomorphism. That means a working programme written in a functional programming language is equivalent to a correct proof done in mathematical logic.
combinatorics—Combinatorics studies methods of counting. These methods are used in algorithm analysis to make estimates of efficiency, namely an algorithm’s space and time requirements. Graph theory makes heavy use of combinatorics, too. Seven Bridges of Königsberg is the best known problem in graph theory, because in solving this tricky, little problem in 1736, Swiss mathematician Euler laid the foundations of modern graph theory.
probability theory—Probability theory studies the likelihood of certain events occurring. Among its famous applications are quantum mechanics, cryptography, non-deterministic algorithms, digital signal processing, data science, and card counting. This subject is not CS specific. Indeed, given its widespread use in all things STEM, is typically taken early in STEM curricula, together with statistics.
automata theory—Automata theory studies automata, also known as state machines. Automata theory is used in formal language theory, compiler theory, computability theory, artificial intelligence, business rules engines, graphical user interfaces, and countless others. The best known application of this theory is the coin-operated vending machine, where an automaton is used to keep track of the amount of money accumulated as the customer inserts coins one at a time, then dispense the item when a sufficient amount of money has been deposited.
compiler theory—Compiler theory studies the process of translating a programme written in a high-level language into an executable programme. A compiler consists of the following stages: lexer, parser, typer, intermediate code generator, machine-independent code optimiser, machine code generator, and machine-dependent code optimiser. The lexer (lexical analyser) recognises the syntactic elements (called tokens) in the input programme, such as keywords, variables, constants, etc. The parser ensures syntactic validity of the input programme, and assembles the lexical tokens into an abstract syntax tree (AST). The typer (type checker) ensures that every expression in the input programme has a type, and hence the programme is semantically valid. Note that the compiler can ensure syntactic validity and semantic validity, but it cannot ensure logical validity; that is the job of the programmer. The intermediate code generator transforms the AST into a machine-independent low-level code. The Java bytecode and .NET CIL are a well-known example of the intermediate code. The machine-independent code optimiser removes bloat and redundancy from the intermediate code. The machine code generator translates the intermediate code into the CPU’s instruction set. The machine-dependent code optimiser optimises the machine code so as to take advantage of the CPU’s hardware capabilities: exploiting instruction-level parallelism, allocating expression variables to CPU registers, etc. Although most CS graduates will never design a language or implement a compiler, this subject is part of the required courses in CS curricula, because compiler techniques such as parsing, optimisation, etc., are useful in many areas of software development, and knowing how a compiler is designed and implemented makes one a more sympathetic programmer.
numerical analysis—Numerical analysis studies methods of numerical approximation. It is used in computing function values, solving systems of equations, differentiation, integration, etc. Newton’s method is perhaps the best known numerical algorithm. It describes a way to find the roots of a real-valued function by successive approximations. While the concepts of numerical analysis are based in calculus, number theory, and the like, the subject devotes much attention to the pragmatics: minimising error accumulation, ensuring numerical stability, making algorithms run fast, and so on. In that respect, this course is a part theory, part practice hybrid.
An algorithm is like a recipie for pudding. But unlike a baker, a computer scientist is not entitled to say, “The proof is in the pudding.” We are obliged to provide an explicit proof that our algorithm not only produces the correct result but also that it runs with reasonable efficiency. Algorithms come from all areas of human activity: growth rate of a population of some organism; scheduling conference rooms; most efficient path for vacuuming a room; shortest route between two cities; equalising audio signals; face recognition; simulating the universe; prime factorisation; board games like chess and go. It is not an exaggeration to say that designing algorithms and proving their correctness is the primary responsibility of a working computer scientist. Indeed, the majority of well-known names in computing have invented algorithms: Knuth, Dijkstra, Kleene, Bellman, Floyd, Hoare, Aho, Hemming, Tarjan, Rabin, the list is endless.
Algorithms are distinguished from business rules. The business rule “A 6.00% sales tax shall be applied to all grocery purchases in this jurisdiction” implements a provision in a tax regulation. This business rule stipulates that the point-of-sale (POS) application developer must sum up the prices of the individual items purchased by a customer, then multiply the sum with 1.06 to obtain the total price. But this trivial calculation requires no mathematical proof.
On the other hand, where an online bookstore application allows the user to sort all books in a category by their publication dates, the developer would employ a sorting algorithm to produce the chronologically sorted list of books. A well-known sorting algorithm is quicksort, designed by the esteemed, English computer scientist Hoare. With a fair bit of algebra and combinatorics, this algorithm is proven to take time $O(n\cdot lg\ n)$, on average. This runtime ranks quicksort among the fastest known sorting algorithms. Of course, such proofs are given by the computer scientist who invented the algorithm, not by the developer who uses it in his code.
algorithmic efficiency—The $O(…)$ above is called the O-notation (O for order of growth), or more formally, asymptotic notation. This mathematical notation is used to describe the efficiency of an algorithm, namely, its memory space and computation time requirements, but in the abstract, without regard to the minutiae like CPU clock speed, cache size, bus width, RAM capacity, and so on.
In this notation, the simplest possible operation is denoted $O(1)$. It is referred to as constant time operation, because it completes in a fixed amount of time, regardless of the input sequence length. For instance, looking up an array element is an $O(1)$ operation, since it takes the same amount of time, regardless of the array length. $O(n)$, where $n$ signifies the length of the input sequence, is an algorithm whose runtime is linear in its input length. That is, the algorithm performs one constant time operation for each element in the input sequence. And $O(n^2)$ algorithm performs $n$ constant time operations for each element in the input sequence, thus the $n^2$. This algorithm takes one million steps to complete the computation on an input sequence of one thousand elements: $1,024^2 = 1,048,576$. In contrast, $O(lg\ n)$ algorithm, where $lg$ is base-2 logarithm, completes the computation on an input sequence of a thousand elements in $lg(1,024) = 10$ steps and a million elements in $lg(1,048,576) = 20$ steps. An $O(lg\ n)$ algorithm is considered very fast. The $O(n \cdot lg\ n)$ runtime of quicksort can be interpreted as performing one $O(lg\ n)$ operation for each element of the length-n input sequence.
The O-notation allows computer scientists to compare the space and time efficiencies of different algorithms in the abstract. For example, $O(n \cdot lg\ n)$ algorithm is appreciably better than $O(n^2)$ algorithm, which in turn is way better than $O(2^n)$, and so on. An $O(n^k)$ algorithm, where $k$ is some constant, is called a polynomial-time algorithm. Commonly used algorithms have polynomial, or better, runtimes. In contrast, an $O(k^n)$ algorithm, where the input length variable $n$ appears as the exponent atop the const base $k$, is called an exponential-time algorithm, and it is considered exceedingly slow. Fortunately, algorithms with exponential, or worse, runtimes are rare in practice.
Common programmes, such as line-of-business applications, social media applications, etc., do not require sophisticated, custom algorithms. And coders who work in these application domains neither know how to design new, original algorithms, nor are they expected to do so; they simply use popular implementations of known algorithms. But specialised application domains, like operating systems, compilers, transportation logistics, etc., usually need novel algorithms. If a need arises, a computer scientist or a mathematician steps in to design the algorithm and to implement the prototype, and the prototype is then handed over to the coders to create the production version.
CS’s reason for being is to solve practical problems using formal, mathematical techniques. Driving forces of CS are curiosity, ingenuity, and utility. Philosophically speaking, even purely theoretical research in CS is motivated by some practical needs—to explain, to innovate, to apply, to have fun.
Solving higher-order problems requires techniques that demand higher-level thinking. The distinguishing feature of higher thinking is the ability to abstract. To abstract something is to understand its essential characteristics, then to give it a name. Named abstractions are reusable generalisations—concepts that apply in many, seemingly-different situations. Reuse yields efficiency and presents opportunities to create by composing various abstractions. Abstract thinking is at the heart of mathematics and, by extension, of CS. The primary means of abstraction are types, which are named sets of values, and functions, which are operations that manipulate typed values.
history—Mathematics was in trouble in at the dawn of 20th Century: numerous paradoxes had been discovered within mathematics, the best known one due to Russell. He discovered in 1901 a paradox at the heart of set theory. In mathematics, a paradox is a statement that is simultaneously true and false. Near the end of the 19th Century, set theory was being touted as the foundation of modern mathematics. Russell’s discovery showed that the theory had a contradiction hidden within, and hence, the whole edifice of mathematics was thus possibly contradictory, inconsistent, paradoxical. Foremost mathematical mind of that era, German mathematician Hilbert, led a bold charge to rid mathematics of all paradoxes. By the late 1920s, Zermelo-Fraenkel set theory managed to excise Russell’s paradox with additional axioms, thereby restraining the excessive generality of set theory. Confidence in mathematics was thus restored. Mathematicians once again grew exuberant; they allowed themselves to believed that all open problems in mathematics will one day be solved.
Then, in 1931, Austrian logician Gödel published his incompleteness theorem. This theorem showed that an internally consistent system of mathematics is incapable of proving all truths that can be stated using valid expressions of this system. Hence, a consistent system is incomplete. It also showed that a consistent system cannot prove its own consistency. This theorem dealt the fatal blow to Hilbert’s optimistic project.
Just as mathematics was facing internal struggles at the turn of the 20th Century, physics, too, was witnessing an all-out, intellectual war between the German Einstein’s classical mechanics and the Dane Bohr’s quantum mechanics. Then in 1927, Bohr’s research assistant, the German Heisenberg, published his uncertainty principle, which showed that it is impossible simultaneously to determine with certainty both the position and the momentum of subatomic particles. Mathematics eventually came to term with its inherent incompleteness, just as physics did with its inherent uncertainty.
computability theory—In this tumult of the 1930s mathematics and physics was born computer science. At the core of theoretical CS is the idea of computability. Computability theory examines which kinds of problems are solvable using a computer and which are not. It is a subfield of mathematical logic. But within CS, asking whether a problem is computable rises to the level of philosophy. In simple terms, a problem is computable, if there exists an algorithm to solve it. But a rigorous proof of computability is an intellectual tour de force. By mid-1930s, there were several theories of computability. Among them, Church’s λ-definable functions and Turing’s automatic machine are the best known, today. Turing subsequently proved that these models of computation are equivalent.
Turing was a brilliant, English mathematician, and very likely the most insightful and imaginative computer scientist, ever. Incidentally, the highest recognition a computer scientist could attain, the Turing Award, is named in his honour. In 1936, he proved that the halting problem is undecidable on a theoretical computation model he conceived, called the automatic machine (a-machine), which today is known as the Turing machine.
The halting problem is a central problem in computability theory. It is the problem of deciding whether a programme, when given an input, would trminate or run forever. Turing’s proof of the undecidability of the halting problem and Gödel’s proof of the incompleteness of mathematics are two faces of the same coin. On a different note, the term Turing-complete means a programming language can simulate any Turing machine. A general purpose language, like Python, can express any algorithm, so it is Turing-complete. But a special purpose language, like regular expressions—which is designed for the special purpose of matching strings, and is used in grep, sed, and related Unix commands—is not Turing-complete.
The Turing machine was the first model for the modern, general-purpose computer. It is equipped with theoretical representations of CPU, memory, and instruction set—the key components of a modern computer. Not surprisingly, the first, practical electronic computer, the Colossus codebreaking machine at Bletchley Park, was based on Turing’s ideas. It was built in 1943 for the express purpose of breaking the German Enigma cipher. It is not a stretch to claim that Turing helped save the Free World.
Also in 1936, American logician Church published his theory of computation, λ-calculus. Church was the mentor of many great computer scientists of the 20th Century—including Kleene, Rabin, Rosser, Scott, and Turing himself. Church contributed and influenced more than anyone to the development of theoretical foundations of CS. λ-calculus is a formal system (a set of rules) that use function abstraction and function application as the means of computation. This is the formal system that underlies functional programming, an approach in which functions are defined, composed, and applied to values in order to produce results, and functions manipulate other functions as values, as well. Note that the word “functional” in this context does not refer to the English adjective meaning “serviceable”, but to the technical noun meaning “higher-order function”, a function that manipulates other functions. In calculus, the differential operator takes a function and returns its derivative. From the CS perspective, the differential operator is not an ordinary function; it is a higher-order function, a functional.
The λ-function (anonymous function) feature found in almost every modern programming language came from λ-calculus. In λ-calculus, the unnamed function that computes the square is abstracted as $λx.x^2$, where $x$ is the formal parameter and $x^2$ the body expression of this anonymous function. When this function abstraction is applied to 3, as in $(λx.x^2)3$, it yields 9 as the result. Lisp, the first functional programming language, can be seen as a direct implementation of some aspects of λ-calculus. For instance, the above λ expression is written in Lisp as ((lambda (x) (* x x)) 3), and when evaluated by a Lisp interpreter, it yields 9. Lisp’s syntax is very close to λ-calculus. And in JavaScript, this expression is written as (x => x * x)(3), and it yields 9 when evaluated in a browser’s JavaScript console. JavaScript’s functional heritage is evident, here.
complexity theory—Another philosophical question in CS is asking how efficiently can a computer solve a problem. Complexity theory is built upon the foundation of computability theory. Whereas computability is concerned with whether a problem is theoretically solvable by a computer, complexity theory is concerned with whether a computable problem is practically solvable by a computer. Complexity theory empowers a computer scientist facing an intractable problem to say confidently, “There exists no efficient algorithm for this problem,” instead of having to whimper feebly, “I do not know an efficient algorithm for this problem.”
The complexity class $P$ is defined as the set of problems that we know how to solve using a polynomial-time algorithm, an algorithm with $O(n^k)$ runtime. The complexity class $NP$, which stands for nondeterministic polynomial-time, is the set of problems that we only know how to verify using a polynomial-time algorithm. From experience, we know that verifying whether a solution to a problem is correct is much easier than solving the problem. For instance, finding the prime factors of 237 is far harder than checking that multiplying two primes, 3 and 79, yields 237. Hence, if it is known that a particular problem belongs to $NP$, the computer scientist would not bother attempting to design an efficient polynomial-time algorithm; instead, he would devote his efforts to designing an efficient approximation algorithm, because he knows that there can be no efficient algorithm that computes the exact solution.
The central problem of complexity theory is the $P\ v.\ NP$, which was posed in 1971 by American computer scientist Cook. It is also one of the most famous, unsolved problems in mathematics. This problem asks whether $P \stackrel{?}{=} NP$. The complexity class $NP$-complete ($NPC$)—which contains the hardest known problems in $NP$—is the linchpin to the $P\ v.\ NP$ problem. $NPC$ has a property that if any problem in it can be shown to have an efficient, polynomial-time algorithm, then all problems in it will have polynomial-time algorithms, and because the $NPC$ problems are the hardest in $NP$, it must therefore be true that $P = NP$. Although no one knows for sure, computer scientists’ gut feeling says that $P ≠ NP$. This belief is often justified by an appeal to intuition: asking whether $P = NP$ is equivalent to asking whether verifying an answer to a hard problem and solving it are equally difficult, or is analogous to asking whether appreciating a performance of a concerto and composing that concerto are equally difficult.
type theory—Type theory is another theoretical and philosophical bedrock of CS. One variety of type theory, the typed λ-calculus, was another of Church’s contributions to CS. Church created typed λ-calculus in 1940, in order to excise paradoxes from his original, untyped λ-calculus which, being much too general, was susceptible to paradoxes, much like 19th-century set theory was. To restrain that excess generality, typed λ-calculus imposes a condition that every λ term must have a type and forbids mixing of types in expressions. In practical terms, a type constrains the range of values an expression can assume and specifies the set of operations that are permitted to manipulate expressions of that type. For instance, a variable of the integer type cannot hold a string value and an integer value cannot divide a string value. Such nonsensical operations were not forbidden in untyped λ-calculus. Paradoxically, that excess power of untyped λ-calculus was its very weakness. Modern, typed programming languages are descendants of typed λ-calculus.
Interest in type theory was traditionally confined to academia. But after years of struggle in building massive web applications using JavaScript, a language with an unsafe, weak, dynamic type system, the industry is slowly, begrudgingly developing an admiration for type theory: all the languages that have become popular in the recent years have safe, strong, static type systems. As such, every CS student must have at least a basic grasp of type theory. If he wishes to gain a deep insight into type theory, though, he will need to study logic and philosophy, as well.
Beyond types, there are kinds. Just as an expression involving values is constrained by a type, an expression involving types, called a type constructor, is constrained by a kind, a higher-kinded type. A type constructor makes new types by combining existing ones, which it takes as input parameters. This is how abstraction hierarchies are built. In Standard ML, for example, the list-type constructor is denoted 'a list, where 'a is the element-type parameter. The value [1, 2, 3] is a list of int elements. It is constructed by applying the type constructor 'a list to the parameter type int, thereby obtaining a new type int list. A parameterised type constructor, like the 'a list list constructor, creates a generic container that can hold elements of various types: a list of integers, a list of reals, a list of strings, a list of records, and so on. Operations that manipulate a generic container neither know, nor care about, the type of the elements. For example, when calculating the length of a list, the type of its elements is superfluous. From the programmer’s perspective, he needs only implement one generic length function to perform this operation, and the language automatically makes the operation work for all element types of list. The means by which the type system achieves this flexibility (and the attendant convenience) is known as parametric polymorphism. Many popular, modern programming languages have this feature.
Functional programming languages that are more advanced than Haskell are indeed few, but they do exist: Coq, Agda, Idris, Lean, and others of the same academic ilk. These languages are known collectively as proof assistants. Coq is a descendant of OCaml, and Agda and Idris are descendants of Haskell. And OCaml and Haskell are offsprings of ML, which was born a language for writing theorem proving tactics (backward proofs) for LCF interactive, automated theorem prover. So, doing proofs is a family business for this lot.
On a more practical note, Coq, Agda, Idris, Lean, and other advanced functional languages support dependent types, which are types that depend on values. By parameterising types with not just types but also values, programmers are able to create much more precise specifications. For example, the type Matrix Float m n specifies a $m \times n$ matrix of floating-point numbers, and only an instance of this type can be added to another instance of this type, since matrix addition requires the matrix dimensions as well as the element types to match. Likewise, transposing a value of type Matrix Float m n must necessarily yield a value of type Matrix Float n m.
In a typical statically typed language, say C++, Java, OCaml, or Haskell, the compiler can check that both matrices contain elements of the same type, but dimension checking is left for the programmer’s code to perform at runtime. But in a dependently typed language, like Coq, Agda, Idris, or Lean, this check is performed by the compiler; no runtime checks are involved. Furthermore, in a dependently typed language, Curry-Hoard isomorphism (types are propositions, programmes are proofs) empowers writing the precise specification, the feature implementation, and the correctness proof all in the same language, and the language’s type system verifies that the implementation conforms to the specification and that it is correct. This level of exactness and correctness are costly, but they are essential in life-critical applications.
Although it is but a small part of CS, the public holds programming in high regard, perhaps because of programming’s perceived impact upon modern society and world economy—analogous to the view of an aircraft carrier as just a boat that floats a small group of naval aviators. For the most part, programming is taught in CS as a practical subject, on the computer in a laboratory. But like other subjects in CS it, too, has a theoretical side: programming language theory. A course on programming languages introduces students to designs and flavours of different languages. But first, let us discuss the historical background of programming.
history—In the 1940s, very first electronic computers were programmed entirely in hardware, by altering signal pathways using patch cords, in much the same way switchboard operators make and break connections in the old telephone network. As programmes grew in size and sophistication, hand-rewiring became impractical. First software-programmable computers appeared in the 1950s, which ran programmes written in assembly language. This was a significant improvement over rewiring. By the 1960s, high-level languages, like FORTRAN, LISP, ALGOL, and COBOL became the norm. (Here, I am using the original, all-caps spellings of these languages.)
FORTRAN (FORmula TRANslator) had features, like complex numbers, vectors, and matrices, which were suited to science and engineering uses. LISP (LISt Processor) was essentially a computer-executable version of typed λ-calculus, so it was employed in mathematical research, like automated theorem proving and rule-based artificial intelligence. ALGOL (ALGOrithmic Language) was an effort to improve the perceived shortcomings of FORTRAN and LISP, and made significant strides in programming language syntax. COBOL (COmmon Business-Oriented Language), with a syntax that resembles English, was a favourite of first-generation, business application programmers.
Today, FORTRAN and COBOL are all but defunct. LISP lives on in the form of Scheme, Racket, and Clojure. And it is the mother of all modern, functional programming languages like Standard ML, OCaml, F#, and Haskell. ALGOL is dead, but its innovations live on: most modern programming languages, even some functional ones, employ ALGOL-like syntax.
programming—The two main flavours of programming language taught in CS today are imperative style and declarative style. An imperative programming language presents an abstracted view of the computer, giving the programmer control over low-level hardware components like CPU registers, ALU operations, and RAM locations. An imperative language is very literal. A programme written in an imperative language gives a step-by-step instruction on how to solve a problem, including how much memory to allocate, how to update portions of the memory, and the like. Profusion of such low-level details obscure what problem the programme is actually solving. Among the early high-level languages, FORTRAN, COBOL, and ALGOL were all imperative langauges. A declarative programming language allows the programmer to describe what the problem is. It is an executable representation of a mathematical description. A declarative language is almost lyrical. The language allows the programmer to say what the problem is, but it figures out the details of how to solve the problem. The programmer has no control over register use, memory allocation, and other the low-level details. LISP was the only early language that was declarative in nature. In general, imperative languages are popular in business applications, and declarative languages are favoured in mathematical applications.
Popular imperative languages can be grouped into procedural and object-oriented families. A procedural language’s primary means of abstraction is to place reusable statements into procedures, and compose the program from those procedures. Well-known procedural languages include FORTRAN, COBOL, ALGOL, Pascal and C. An object-oriented (OO) language models real-world concepts as interacting objects. For instance, a banking system may model customer, teller, queue, account, etc., as objects, and the interactions among them collectively express the dynamic behaviour of the whole banking system. Most modern, imperative languages are OO in nature. Best known OO languages are Simula, Smalltalk, Objective-C, C++, Java, C#, JavaScript, and Python.
Popular declarative languages can be grouped into logic, query, and functional families. A logic programming language allows the programmer to create a set of complex rules, and automatically infers a conclusion from those rules. The best known logic programming language is Prolog. A query language allows the user to describe the desired result as a collection of conditions. The best known query language is SQL. A functional programming (FP) language uses types and functions that operate on those types as means of abstraction. The best known FP languages are LISP, Scheme, Standard ML, OCaml, F#, Haskell.
Virtually all modern languages have both FP and OO features: JavaScript, TypeScript, Python, Scala, Swift, Kotlin, OCaml, F#, Reason, the list is long. Most CS curricula today are industry-oriented; they teach imperative, OO languages that are in high demand. Popular teaching OO languages are JavaScript, Python, Java, and C#. But a few foundations-oriented curricula, which fortunately still exist, teach declarative languages with an emphasis on FP. Popular teaching FP languages are Scheme, Standard ML, OCaml, and Haskell.
When CS students say “lab work”, they mean doing programming assignments. A typical assignment is small—a few minutes worth of work for an experienced programmer. But for novices, an assignment can take several hours to complete. Given the breadth of the CS curriculum, it is impossible for students to devote the time necessary to become industry-ready programmers. Hence, those who plan to enter the industry after graduation should study on their own, implementing personal projects more ambitious than class assignments.
A majority of programming assignments focus on implementing well-known algorithms, starting with simple sorting algorithms, progressing through elementary graph algorithms, culminating in advanced, optimisation algorithms. Given the online resources available today, programming assignments have degenerated into cut-and-paste exercises. A serious student should attempt to solve the problems on his own first, before seeking solace in ready-made code, online.
process—Software development process management refers to the methods by which technical managers steer large projects. A typical project lasts years, and involves tens, or even hundreds of individuals with differing capabilities and varying levels of competence. Every large IT organisation has its own development process tuned to its corporate culture.
This is a subject that is hard to teach, and even harder to learn, in a semester-long course. But the underlying philosophy of a software development process is simple: software development is inherently unpredictable, so work in small increments, and quickly pivot when the unpredictables inevitably erupt. These small increments are called iterations, and they generally last two or three weeks. This allows the team to assess and address the risks in a timely manner, before they spiral out of control and endanger the project. Let us call this large-scale development process that guides the actions of the team the external process, in order to distinguish the other process that is never taught in the CS curriculum—the internal process.
Whereas the external process governs the conduct of the entire team, the internal process drives the actions of the individual team member. Indeed, each programmer develops his own internal process, in accordance with his personal sense of aesthetics, ethics, skills, and experiences, as well as his work environment. Because a programmer’s internal process is left up to the individual and is never taught, it is often haphazard. But it can be made more orderly by emulating how a mathematician does mathematics: deepening understanding of existing concepts and expanding boundaries by creating new concepts.
Understanding of existing concepts can be deepened using the following techniques:
Existing boundaries can be broadened by deriving new concepts using the following techniques:
fold operator.engineering v. art—Many refer to software development as “software engineering”, and they call themselves “software engineers”. This is a misnomer: programming is not engineering; the closest calling to programming is art. The key differences between engineering and programming are as follows:
Systems studies are the more practical face of CS. Major subjects in this speciality include computer organisation, operating systems, networks, information security, databases, information retrieval, and computer graphics. These subjects are closely tied to programming. The most prevalent system programming languages are C and C++. Rust, a newcomer, is touted as the next system programming language.
computer organisation—Computer organisation is usually taught to first-year, first-semester CS students. It introduces the major components of a computing environment, like processor, memory, graphics card, network card, disc drive, print server, disc server, network switch, network gateway, etc., and how they interact with one another. This course may have been necessary decades ago when only large organisations owned computers, but it is not as important today when many new CS students are already well-versed in computing infrastructure and programming languages. So, it is sometimes folded into an introductory programming course.
operation systems—An operating system (OS) is a programme that controls how a computer’s hardware resources—CPU, GPU, ROM, RAM, SSD, NIC, etc.—are used by programmes running on that computer. The OS runs continuously in the background, from startup to shutdown. It runs at the highest priority, so no other programme can interfere with its operation. A general-purpose OS, like Linux, macOS, and Windows, aims for responsiveness of the GUI. A real-time OS, on the other hand, enforces orderly and predictable execution of programmes. Real-time OS is used on complex, embedded systems, such as those that run factories and power plants.
A typical course teaches the design of an OS kernel, typically Linux or Unix, covering topics such as scheduling, parallelisation, caching, file system, and device driver. Programming assignments are mostly in C, and deal with narrow aspects of various algorithms, so as to keep the complexity of the assignments manageable.
communication networks—Networking technologies are built as layers of protocols, each layer using the services provided by the one immediately below, in order to provide its own services to the one immediately above. The protocols are grouped into application, transport, internet, and link layers. This pantheon of protocols is referred to, collectively, as TCP/IP.
The application-layer includes some of the most famous protocols: HTTP, SMTP, DNS, etc. An application-layer protocol is like a domain-specific language; it implements application functionality and encodes application data for transmission. When transferring the data, the protocol breaks up the data into a sequence of packets and hands them over to the chosen transport-layer protocol. The two best known transport-layer protocols are the TCP connection-oriented transport protocol which emphasises reliability and the UDP connection-less transport protocol which emphasises immediacy. The internet-layer protocol (IP) is responsible for conveying transport-layer packets from the origin computer to the destination computer, through multiple intermediate computers. IP conveys all TCP packets along their pre-determined path and in their original order, but for each UDP packet, it chooses the most time-efficient path. The link-layer protocols, which include ARP, MAC, Ethernet, and WiFi, are responsible for sending packets over the transmission medium, the wire or the radio channel, of the network.
An introductory course in communication networks teaches mainly TCP and UDP transport-layer protocols, their design and their uses. This course also introduces students to traditional client-server programming, often in C. An advanced course explores the innards of the Internet, covering internet-layer protocols like IP, ICMP, and IGMP. More advanced courses teach the design of modern networking technologies, such as LPWA, LoRa, ZigBee, cellular, satellite, and the like.
computer security—The umbrella term “computer security” encompasses data integrity, data authenticity, user authenticity, OS security, privacy, encryption, key distribution, and many other related concepts.
A theory-centric CS curriculum focuses on the mathematical aspects: encryption algorithms, key distribution algorithms (private key or public key), data integrity (assurance that the data have not been tampered with), and data authenticity (assurance that the data originated from an authenticated source). A practice-centric CS curriculum covers operational aspects of computer security: key stores, OS security, intrusion detection, penetration testing, user authentication protocols, and the like.
database systems—A database (DB) is a data storage that guarantees integrity and consistency of the stored data and efficient retrieval thereof. Two main types of databases are hierarchical and relational. With the rise of business computing systems in the 1960s came the hierarchical databases. In this model, records are held in containers, and containers are held in still larger containers, in a hierarchy. For example, a company contains departments, and each department contains employees. The advantages of the hierarchical model are its resemblance to real life and its implementation simplicity. The main disadvantage is the inefficiency associated with having to traverse the hierarchy from the top, all the way down to the needed record. Then, in the 1970s, relational databases began to displace the hierarchical ones. The term “relation” refers to the set-theoretic concept of relation, which describes an association between two or more sets. In the database, sets are represented as tables and set elements are represented as records. For instance, the fact that an employee works in a particular department is a relation from the employee to the department (one-to-one relation), and its inverse relation states the fact that the department employes this employee, and possibly many others (one-to-many relation).
A typical DB course covers only relational databases. In addition to teaching the SQL query language, this course covers the design of the database, including how the data are stored on disc. In recent years, however, hierarchical database has returned to prominence, with the advant of JSON and XML document stores that are popular with modern web and business applications.
information retrieval—Information retrieval (IR) is the collection of techniques that query information. Although an IR query is conceptually similar to a DB query, their implementations and uses are very different. Whereas a DB query uses a precisely crafted query to retrieve only the specified pieces of data from a structured source, an IR query compares imprecisely specified query with all known sources, including unstructured sources, and returns the results in order of relevance. The more precisely composed the query, the higher the relevance of the matches, and the smaller the result set. The best-known implementation of IR is Google’s web search engine.
A course in IR usually focuses on mathematical techniques. Commonly, a document about a particular topic is represented as a vector in an n-dimensional vector space $R^n$. Each distinct concept within that topic is then represented as a dimension of that vector space. The document vector $d = [c_1, c_2, …, c_n]$, where $c_j$ are the component concepts, is constructed by counting the frequencies with which the individual concepts appear in the document. The relatedness of documents $d_1$ to $d_2$, called the similarity cosine, is computed as the vector dot product $d_1 · d_2 = \mid d_1 \mid \mid d_2\mid cos θ$, where $\mid d_i \mid$ are the magnitudes of the vectors and $θ$ is the angle between the vectors. If the two documents are strongly correlated, their two vectors are nearly aligned. As such, $θ$ is almost 0° and their similarity cosine is almost 1.0. But if the two documents are uncorrelated, their two vectors are orthogonal. Hence, $θ$ is 90° and their similarity cosine is 0.0. In this way, the query’s similarity to the known documents can be computed, and the matched documents can be ranked by their similarities to the query. IR is simple in theory, but real-world implementation issues are decidedly complex. Google’s techniques for Cataloguing the Web are efficient, sophisticated, expansive, tamper-proof, and proprietary. Such practical aspects of IR are not suited to the classroom setting.
computer graphics—Computer graphics includes 2D and 3D polygonal graphics, and 3D volumetric graphics. Some curricula may also include information visualisation under computer graphics. GUI frameworks and drawing applications use 2D polygonal graphics. VR games, flight simulators, and racing simulators use 3D polygonal graphics. Realistic cloud renderings, ray tracing, and weather modelling use 3D volumetric graphics.
In 3D polygonal graphics, a modelled object is constructed from surfaces fashioned from triangles. The model’s bare surfaces are then covered with photographs of the real-world object that the model represents. The simulator animates these objects within the modelled space. Although the model looks realistic, its insides are hollow. Hence, the model’s weight and density are mere hard-coded approximations. In contrast, 3D volumetric graphics models the space as a dense field of real or complex numbers. In a weather model, for instance, each point in the modelled volume may represent atmospheric pressure and temperature, particulate concentration, and wind speed vector, among other quantities. The simulator may then animate this volume using physics-based computations. Accurate mass and density solids and gases may be computed from the local data points.
Naturally, volumetric computations require orders of magnitude more computing power than comparable polygonal computations, with commensurate increase in accuracy. Information visualisation uses 3D volumetric graphics. The modelled volume represents the entire information space, and each point in the volume represents a document. And the spatial axes of the volume represent various topics of interest.
CE is a cross between CS and EE. The emphasis of CE is in the design and manufacture of computing hardware. Its theoretical foundations are drawn mainly from EE. A CE curriculum also covers the practical aspects of CS, with focus on algorithms and their implementations in hardware. Some CE curricula emphasise the CS aspects, while most emphasise the EE aspects.
Information theory is concerned with efficiency, reliability, and security of information storage and transmission. This subject became a formal speciality in the 1940s under the American electrical engineer Shannon, who is one of the most revered in the field. How electrical engineers use information theory to analyse communication systems is analogous to how computer scientists use combinatorics to analyse algorithms. The O-notation gives estimates on space and time requirements of algorithms in the abstract, thereby allowing computer scientists to select the best design for an efficient, correct algorithm. Similarly, information theory gives mathematical expressions of information content, transmission channel capacity, error rates, etc., in the abstract, thus enabling electrical engineers to select the best design for an efficient, reliable communication system.
Although information theory is affirmatively an EE subject, it is studied in CS in the form of data compression and data encryption algorithms. Well-known applications of information theory are compression formats like ZIP and JPEG and cryptographic protocols like SSH and SSL.
A number of elementary electrical engineering subjects that pertain to computing are taught as CE. Typical courses in this area include analogue and digital circuits, integrated circuits, antenna theory, transmission line theory, processor architecture, digital signal processing, and embedded systems.
circuit analysis and design—Analogue circuits course teaches about designing circuits using resisters, capacitors, inductors, and transistors, where input and output signals are analogue in nature. Digital circuits course teaches the design of logic circuits, like those inside of a CPU. Integrated circuits course teaches the design and fabrication of chips, covering topics like layout, packaging, heat dissipation, etc.
processor architecture—Processor architecture course teaches the instruction set architecture and the microarchitecture. It covers topics such as instruction set, ALU, control unit, registers, pipelines, caches, on-chip buses, and so on.
Some CE curricula might even include quintessential EE subjects like antenna theory and transmission line theory. Antenna theory teaches the design and operating characteristics of various types of antennae. Many components inside a computer emit electromagnetic waves, so a computer acts like a transmitter. As such, the components must be shielded in order to prevent radio interference. Transmission line theory teaches how electromagnetic waves travel in wires and waveguides and techniques for preventing signal degradation and reflections. Transmission lines are everywhere in a computing system: network connections, peripheral cables, motherboard buses, and CPU internal buses. On-chip, high-speed buses are particularly problematic for design engineers, given their microscopic size, proximity to one another, high heat inside the chip, and GHz-range operating frequencies. Although a computer scientist does not have to deal directly with antennae and transmission lines, he should nevertheless possess the theoretical understanding thereof, given their significance to the design of computing hardware.
digital signal processing—DSP course teaches mathematical techniques used in signal processing, starting with Fourier transform and Z-transform. This subject requires fairly advanced engineering mathematics. Even in the EE curriculum, it is usually taught in the senior year. Embedded systems course teaches microcontroller-based implementations of digital filters, feedback control systems, neural networks, Internet of Things (IoT), etc.
microcontrollers and single-board computers—Microcontroller units (MCUs) are embedded into toys, appliances, cars, and just about every modern, consumer product. An MCU is a low-cost microprocessor chip. An MCU performs the role of the CPU in a programmable, digital circuit, which comprises ROM, RAM, and a power regulator. Fully-assembled, ready-to-use MCU boards are also available, some as small as a postage stamp. Single-board computers (SBCs) are the mainstay of IoT implementations. An SBC is a fully functional computer on a single circuit board. Some SBCs can be as big as a small briefcase, but most are smaller than a large wallet.
The differences between an MCU and an SBC are processing capabilities, external signal interface versatility, power consumption, and cost. MCUs are designed for simple, but large-scale, applications where low power consumption and low unit price are critical. The control circuit inside a typical washing machine is an example of an MCU-driven circuit. SBCs are intended to serve as local servers in small-scale sensor networks, so they require processing capability and interface versatility, and as such more costly than MCUs.
The Arduino platform is popular with CE curricula, because it allows students to explore analogue circuits, digital circuits, and microcontroller programming, simply and cheaply. The Arduino board comes complete with onboard EPROM programmer, power regulator, 8-bit microcontroller, analogue-to-digital (A/D) converter, and digital-to-analogue (D/A) converter. The board can be programmed from a laptop via a USB cable, can power external circuits, and can communicate with external circuits using several industry-standard interface protocols over general-purpose I/O (GPIO) pins. The board is programmed in a language called Processing, which is simplified Java. An Arduino clone costs as much as a cup of latte.
Another popular learning platform is the Raspberry Pi. The Pi is a single-board computer. Although its size is about the same as that of the Arduino, the Pi is a full-blown, 64-bit computer. It is fit to serve as a low-cost, 4K-video-capable, GUI desktop computer, either in classroom or in bedroom. But just like the Arduino, it has GPIO pins that can communicate with external circuits. Because the Pi is a computer that can run Linux, BSD, and Window, it can be programmed using any language. The Pi Zero, the cheapest Pi board, costs about the same as a genuine Arduino Uno, the most popular Arduino board.
The micro:bit is not as popular in the US, but it very popular in the UK, because the government gives out free micro:bit boards to school-age children. The micro:bit is a tiny microcontroller board with a 32-bit, 16 MHz ARM Cortex-M0 CPU, 256 KB flash memory, 25-LED display, accelerometer, magnetometer, Bluetooth radio, two buttons, GPIO pins, and an onboard MicroPython runtime. Although the micro:bit has fewer GPIO pins than the Pi and the Arduino, its built-in support for Python along with its onboard buttons and LED display make the micro:bit the ideal platform for children. Its ecosystem, naturally, leans toward child-friendly, robotic toys. The micro:bit costs the same as the genuine Arduino Uno.
Advanced students should look at the STM32 Black Pill board. It costs about $1.00 per board, and cheaper in bulk. It uses the ARM Cortex-M4F, a stout, little 32-bit MCU clocking at 100 MHz, with a built-in FPU, 512 KB of flash memory, and 128 KB of SRAM. Since the Black Pill has no MicroPython runtime like the micro:bit, this amount of flash memory is more than enough for storing complex programmes. It also supports all the standard I/O protocols. It can be programmed using several popular languages, including Processing, C, Go, and Rust. Those who have a well-equipped electronic workbench at home, this board is undoubtedly the most practical and economical choice for design experimentation and for production application.
A bachelor’s degree does not mark the end of learning; it merely indicates that the graduate was deemed to have acquired all the rudiments of further learning in that field. Further learning does not mean graduate degrees, per se; it means life-long learning, in whatever form. That is, even if one attained a PhD in the field, he must not stop learning. This is one of those dirty, little secrets of life.
Reading was, is, and will be the primary means by which one learns. Given the breadth of CS, there is rather a lot to read, and the amount of required reading increases exponentially at the graduate level. Hence, a student must learn to read fast, from the very beginning. By “fast”, I do not mean “super-fast”, but “ordinary-fast”—being able to finish in under 60 seconds one printed page of this article, which is a simple, factual document that demands little analytical thinking from the reader. The slower the reading speed, the less connected the concepts appear, and the less interesting they are. Loss of interest hinders one’s ability to absorb the material, which leads to loss of confidence, and eventually a distaste for reading. Slow reading is, thus, a life-long debility.
A typical semester lasts a dozen or so weeks, and the syllabus is split into week-long packets, each week covering three chapters or thereabouts. The entire packet should have been studied, before that week’s classes begin. A graduate student can certainly read a week’s worth of reading assignment in one sitting. But an undergraduate student usually cannot, because at his level, almost everything he reads is new and strange. As such, he must read the week’s packet in multiple sittings, starting preparations for the following week during the current week, if the weekend is insufficient amount of study time. Obviously, reading ahead during holidays is a must.
News articles can be read fast by skimming—reading only the topic sentences in each paragraph. But this technique cannot be used to follow reasoning chains commonly found in academic texts. To study a reasoning chain, one must read each argument carefully, analysing its premise, its implications, and its conclusion. Otherwise, the conclusion cannot be understood, fully. In a mathematical text, whole sections are reasoning chains, so skimming will not do. And when reading research papers as a graduate student, ability to analysis carefully the arguments is of vital importance. Failing to spot holes in arguments or breaks in argument chains will cause the reader to accept the author’s wrong conclusions. So, details are important in STEM reading.
One technique for efficiently absorbing large amounts of details is multi-pass reading, which comprises setting, scanning, skimming, and scrutinising stages.
setting—Before sitting down to read, set a goal for the session. A goal can be as modest as learning one algorithm (one section) or as grand as understanding a complex concept (multiple chapters). Without a goal, the mind is doom to wonder aimlessly across the pages, absorbing not much of anything—a waste of time and effort.
scanning—When picking up an unfamiliar textbook, scan the entire book: read the front and the back covers; read the table of contents; read the preface; and quickly flip through the whole book, noting titles, tables, figures, and appendices, but without wallowing in the details. Knowing the author’s professional background is important, because his background inevitably shades his perspective in presentation. The reader now has an idea of the scope of the textbook and knows the key terms of the subject, even if he does not understand the full meaning of these terms.
skimming—Now, skim the assigned chapter. Start by reading carefully the introduction section. Next, skim the subsequent sections, picking up more key terms and scraps of information, without getting bogged down with the details like mathematical proofs. Then, read carefully the conclusion section. At this point, the reader knows the context and scope of the chapter, that is, the specific area it occupies within the whole subject; sequencing of concepts; key terms involved; and relationships between those terms.
scrutinising—Armed with this contextual background, the reader is now ready to scrutinise the chapter. Read thoroughly every section, especially the proofs. Where appropriate, make annotations in the textbook. These handwritten annotations jog the memory in subsequent readings. The chapter must be reread later, at least once more, because complex concepts cannot be understood fully in one sitting. Also, take notes in a notebook. Mathematical textbooks authors have a nasty habit of making huge logical leaps in proofs. Mathematicians breathe and eat mathematics. As such, concepts in mathematics, especially the undergraduate-level ones, are painfully obvious to them. So, when they speak mathematics, they are prone to leave out the “obvious” bits that are part of their shared experience. Unfortunately for a novice who does not share that experience, those details are not at all obvious. The student must, therefore, work out those details in his notebook. Textbook authors also have the habit of shunting the details to the exercises, where they give tantalising hints. If time permits, do those exercises, even if they are not assigned. Other details are buried in the appendices, so study the appendices, too. Still other details must be chased in other textbooks or in online sources. Do what is necessary to understand the whole topic, thoroughly. After completing the chapter, skim it one last time. This final step can often spark deeper insights into the topic.
switching—There is a trick of the mind known only to those who habitually read for long hours. Studying is an exertion that saps the mind and drains the body. To prevent tiredness and to mitigate distractions, study in a quiet room, keep the room at a comfortable temperature, and take regular, short breaks. But after studying one subject for a few hours continuously, the mind loses its ability to concentrate and absorb, even if the body remains in good nick. This is the time to switch to a different subject. Faced with a fresh challenge, the mind is once again ready to absorb more information.
Remember these:
Every STEMer must write, be they in academia or in industry. Master this art as early as possible. High-achieving students would have become competent writers in middle school and accomplished writers by high school. But technical writing, especially of a mathematical persuasion, is unique. The easiest way to learn to write well is to read plenty of peer-reviewed papers and textbooks by notable professors. Writing is inseparable from reading.
academic writing—Academic writing is part of daily life in STEM. In academia, researchers publish scientific papers. A typical peer-reviewed paper is a few tens of pages in length. PhD candidates must produce new, original works describing their theses. A thesis is usually a few hundred pages in length, about as long as a book. Academic writing in the form of a scientific paper or a thesis begins with an abstract that declares the goal and scope of author’s new, unique work. The introduction provides a brief history of the topic and a short survey of existing works. Next, the author highlights the novelty of his approach. He follows this with a detailed description of his work. In addition to mathematical proofs, he must include enough details to enable others to reproduce his experiments and to verify his results. He concludes by summarising his results. He points out the superiorities and the shortcomings of his work compared to the state of the art. And finally, he enumerates potential improvements to his work and possible further research directions.
business writing—Business writing comprises many document types: user manuals, requirements documents, design documents, technical reports, business proposals, collaboration agreements, and regulatory compliance certifications. But they all follow a set pattern. A document begins with title, organisation name, distribution list, references to related documents, references to relevant laws and regulations, and update history. The author then introduces the purpose of the document. The main body of the document depends on the purpose, naturally. User’s manual describe workflows processes and tasks therein, along with screenshots of the user interface. In scientific or technical sectors like research laboratories, aircraft manufacturers, etc., requirements, design, and similar documents may well resemble scientific papers in their rigour. Collaboration agreements, regulatory compliance certifications, and similar writings follow legal documents in structure and style. If such documents are drafted by STEMers, they will subsequently be reviewed and edited by lawyers.
Remember these:
Every CS student must complete programming assignments. Even a theory-oriented course has programming assignments, but they usually focus on implementing specific algorithms. As such, they tend to be small and isolated. On the other hand, assignments in a practice-oriented course are accretional. They require the student to build upon and expand earlier assignments. This simulates an industrial software project, albeit on a far smaller scale. In these courses, if the student fails to complete earlier assignments, he will be unable to complete the later, more difficult ones. Some semester-long projects may require multiple students to collaborate. In such situations, risks of failure increase exponentially. If one student fails to complete his assignment, the whole project will fail, and hence the whole team fails. But this type of project-oriented assignments are rare, for good reasons. In this section, we shall examine the nature of programming.
creativity—Creating a programme is very similar to crafting a prose:
Hence, programming is not a mere trade for earning remunerations. And although it is encrusted with indicia of technology, like algorithms, code, computer, IDE, etc., programming is an art, a solo, creative endeavour. A well-designed programme exudes elegance, much like a well-composed prose. A programmer who works only 8 hours a day on a problem is not an artist, but a tradesman. A programmer would do well to take pride in his art as much as a novelist does in his.
productivity—Most people in IT, especially managers, measure productivity with lines of code. In truth, lines of code on the computer is meaningless, when the programmer who wrote those lines does not possess a full, mental image of his work. The programmer, by definition, knows the solution space. But for him to produce a good solution, he must understand the problem space, adequately. The habit of skipping problem analysis and jumping headlong into solution design in hope of beating the clock is a career killer. Do not develop this habit.
efficiency—Substantive efficiency arises from well-designed algorithms, not from hand-tweaked code. In programming, there is a saying, “Get it right; then, get it tight,” meaning solve the problem correctly, then optimise it if necessary. A programme that runs fast but produces inaccurate results or crashes often is more worthless than the one that was never written in the first place.
longevity—All useful programmes require non-stop maintenance. This is the main difference between a piece of literary work and a programme. A writing, once published, is fixed in perpetuity. A programme’s useful lifecycle begins at publication. For a programme to maintain its usefulness, it must be updated continuously: adding new features, fixing errors, patching security holes, reworking to keep pace with changing business needs, etc. Often, a programme’s maintainers are different from its original creators. So, when creating a new programme, be attentive to the needs of the future maintainers: include succinct but actionable comments.
Before deciding to study CS, a young person should ask himself what it is about this discipline that he finds appealing. If coding is all that he is interested, the CS curriculum will be frustrating, perhaps even infuriating, to him. For example, if he is only interested in mobile game development, he should study programming from a book and spend his time honing his coding skills by writing games. If he is interested in enterprise applications, studying business administration and teaching himself programming might well be better for him. If he is interested in weather modelling, he should study meteorology and learn programming on the side. And if he is interested in self-driving cars or autonomous robots, it is better for him to study engineering, and pick up programming on his own.
On the other hand, in addition to his love for programming, if he wants truly to understand what types of problems are computable, what makes algorithms efficient, how to design new, better programming languages, and the like, CS is the right choice for him. Note also that it is not uncommon for STEM graduates with degrees in mathematics, physics, or engineering to attend CS graduate school. Their broader background and perspective are a significant advantage in their future CS careers.
In this section, I enumerate a list of books that I recommend for CS students. I can only recommend books that I have read either when I was in school or thereafter. And I may not have read the best books in all the subjects. Moreover, your mode of learning may differ from mine. So, use this list not as the ultimate collection, but a starting point to discover great works in CS. Most of all, remember that you need not read all these works while you are studying CS; many of them should be read over the course of your CS career. For this reason, I provide when you should read a particular book.
Overview of CS
Mathematical Foundations
Algorithm Analysis
Philosophy of CS
Programming
Systems
Information Theory
Hardware Engineering
Reading and Writing