Ordinary Mortals and CS education

This post can also be read as a public Google doc.

I’ve written Computing for Ordinary Mortals for readers without a technical background or even much experience in computing. My thought was this: If you wanted to explain what computing is all about, starting from scratch, what what would you say? You have a tremendous number of decisions to make, about which topics are critical and which can be left out, about the ordering and detail of topics you include, and about how the topics fit together into a comprehensive whole. For what it’s worth, some computer scientists will make decisions different from mine. Most popular science books and textbooks go into greater detail about representing and managing data; I delay a discussion of programming concepts until after algorithms and abstract data types; I punt on the question of whether computer science is a branch of applied mathematics (see Dijkstra’s “How do we tell truths that might hurt?” [PDF], though he was talking about programming), or a branch of science (Newell, Perlis, and Simon’s “What is computer science?”), or a branch of engineering (Eden’s “Three Paradigms of Computer Science” [PDF]), or perhaps something different (Rosenbloom’s On Computing, or Graham’s “Hackers and painters”).

Writing a popular science book on computing means taking a stand on such issues, but the constraints of the genre didn’t make it easy for me to say, “Here’s what I’m doing...” That’s in part what this document is for, to identify the connections between Ordinary Mortals and the field of computer science, at least as it’s currently taught at the university and secondary school levels.

The first section of this document contains a selection of quotes from the book, indicating what I think are the most important points covered in each chapter. The second is a mapping of the concepts in the book to the knowledge areas described in the computer science curriculum guidelines produced  by ACM/IEEE. The third section is a very rough mapping of the concepts in the book to the AP’s Computer Science: Principles framework.

I should note that Ordinary Mortals takes a computer science perspective on the areas that it covers, rather than exploring social or philosophical implications (much less how to use computers). This is most obvious in the last two chapters: AI is described in terms of agents and environments, search and optimization, rather than philosophical questions about whether machines can be intelligent; HCI is treated as an area of software engineering, excluding most of the other areas that it encompasses, such as design, applied cognitive science, and so forth.

Ordinary Mortals in Less Than Two Pages

Suppose you have just a few minutes rather than a few hours to read Ordinary Mortals... Here’s a pocket summary.

Ch. 1: Getting Started
The purpose of computing is insight, not numbers. [Hamming]
The content areas of computing include “design (which covers hardware and software systems), practice (which includes the work of computing professionals who envision, build, and manage such systems), and mechanics (which encompasses the abstract concepts [of computer science]).”
“[R]ecognizing a natural correspondence between [real-world] situations and what’s known about the theory and practices of computing... is part of what’s sometimes called computational thinking.”

Ch. 2: From Mechanical to Electronic Computers
“[C]omputing is the study of abstract models of the structure and control of discrete processing systems.”
“[C]entral concepts in computing [include] the encoding and decoding of information in different forms, discrete processes, control, and modularity as a tool for reducing complexity.”

Ch. 3: Computer Architecture: The Nuts and Bolts
Processing concepts include “faster clock speeds, specialized co-processors, multiprocessing, pipelining, and sets of uniformly fast instructions.”
Storage concepts include “the storage hierarchy... caching of information... the locality principle...”
I/O concepts include “interrupts” and “sending appropriately encoded information to video memory.”

Ch. 4: Algorithms and Structured Data: Solving Problems
“We’ve seen different kinds of structure in information, which can be captured by abstract data types.”
“We’ve also seen algorithms for processing information structured in different ways: traversal, searching, sorting, finding paths...”
Algorithm characteristics include “brute force or divide-and-conquer strategies, and different abstract ways that we can describe algorithms that rely on these strategies—this one might produce optimal results, this other one is greedy.”

Ch. 5: Programming: Putting Plans into Action
“We’ve learned how to read a program, to follow the syntax to understand its procedural structure and how its information is organized.”
“Much of [programming] happens in your head as you figure out how to approach a problem: how to break it down into smaller pieces, how those pieces should interact, and how they come together in a reasonable design.”
“Variable assignments. Control flow in terms of conditionals (if-then statements), iterations (loops), and transfer of control to other procedures. Data structures.”

Ch. 6: Operating Systems: Working Together
“To understand the complexities [of an operating system], we need new concepts: processes, resources, and policies that govern their interaction.”
“… for processes we think in terms of scheduling policies...”
“Space must be managed just as carefully as time in an operating system, but the strategies are different.”

Ch. 7: Computer Networks: Making Connections
“The first [concept] deals with how activities are organized in the network, in layers of services.”
“The second concept is that of a protocol.”
“...a set of ground rules for a new approach to networking, which led to the Internet of today...”

Ch. 8: Theoretical Computer Science: Pushing Boundaries
“If a model [of computation] is a close enough match for a real computer, then the conclusions we draw about the model also apply to the computer...”
“Surprisingly, we’ll discover that... some things can’t be computed.”
“We also look at problems that we know can be solved, to ask how easy or hard they are... Again, surprisingly, we’ll find that for some interesting and important problems, we can only guess how hard they are.”

Ch. 9: Artificial Intelligence: Being Smart
“Two important abstractions in AI are environments and agents.”
“[Search] is an essential part of intelligence... Reasoning from what is known is also an essential part of intelligence... We now have learning, a third element of intelligence.”
“We can think of some problems in terms of optimization.”

Ch. 10: Human-Computer Interaction: Thinking About People
“… one of the core questions in human–computer interaction... is usability... Effectiveness... Efficiency... User satisfaction...”
“… three basic strategies for design: focus on users from the start, test the system with users as it’s being built, and change the design to reflect what’s learned.”
“The central theme in HCI is that people matter.”

Ordinary Mortals, CS2013, and CC2001
Imagine teaching an introductory course in computing, either for majors or non-majors. Ordinary Mortals wasn’t written to be a textbook, but a course could be structured around it, with the overall goal being to give a broad outline of the field.

Where would such an outline come from?  The Computer Science Curricula 2013 Knowledge Areas (CS2013), by the ACM/IEEE-CS Joint Task Force, gives the following breakdown of topics:

AL	Algorithms and Complexity
AR	Architecture and Organization
CN	Computational Science
DS	Discrete Structures
GV	Graphics and Visual Computing
HC	Human-Computer Interaction
IAS	Security and Information Assurance
IM	Information Management
IS	Intelligent Systems
NC	Networking and Communication
OS	Operating Systems
PBD	Platform-based Development
PD	Parallel and Distributed Computing
PL	Programming Languages
SDF	Software Development Fundamentals
SE	Software Engineering
SF	Systems Fundamentals
SP	Social and Professional Issues

That’s a lot of ground to cover. Ordinary Mortals introduces basic ideas in these areas, though it doesn’t contain anywhere near the rigor or detail of real computer science courses. The table below shows how coverage is balanced across the content areas, and it gives all the italicized terms in each chapter.

Legend:

Chapter	Chapter title
%	Percentage of text in the chapter, relative to the main body of text
CS2013	Relevant Knowledge Area and percentage of credit hours in the undergraduate computer science curriculum, as given in the CS2013 document; italicized KAs indicate light to minimal coverage
Concepts	The main focus and supporting concepts covered in the chapter.

Chapter	%	CS2013	Concepts
Ch. 1. Getting Started	5%	SF (9%)	Main focus: definition of computing (design, practice, mechanics), computational thinking. Supporting concepts: hardware, software, computer architecture, programming, software engineering, communication, coordination, information management, artificial intelligence, theory of computing, debugging, secondary storage, indirection.
Ch. 2. From Mechanical to Electronic Computers	8%	DS (13%) SF (9%) AR (5%)	Main focus: states and discrete systems, control, abstraction, encoding, modularity. Supporting concepts: binary, binary counting, instruction, von Neumann architecture, input devices, memory, controller, arithmetic/logic unit, output devices, central processing unit, program.
Ch. 3. Computer Architecture: The Nuts and Bolts	10%	AR (5%) SF (9%) GV (1%)	Main focus: instruction cycle; efficient processing: multiprocessing, pipelining, fast common case (RISC); efficient storage: storage hierarchy, caching, locality principle; I/O: interrupts. Supporting concepts: registers, system bus, instruction set, program counter, flow of control, parallel computing, distributed computing, memory, RAM, locations, addresses, secondary storage, byte, temporal locality, spatial locality, predictive caching, input devices, output devices, interrupts, pixel, computer graphics, modeling, rendering, animation.
Ch. 4. Algorithms and Structured Data: Solving Problems	14%	AL (9%) DS (13%)	Main focus:  abstract data types: sequence, tree, graph; algorithms:  traversal, search, sorting; algorithm characteristics: brute force, divide-and-conquer, greedy, optimal solution; recursion, encapsulation. Supporting concepts: representation, input, output, elements, index, nodes, vertices, links, edges, parent, children, root, leaves, path, sequential/linear search, binary search, sorting, selection sort, decrease-and-conquer, Quicksort, depth-first traversal, breadth-first traversal, minimum spanning tree, cost, optimal solution, small-world network, semantic network, spreading activation, priority queue, stack, tuple, relational database, query.
Ch. 5. Programming: Putting Plans into Action	12%	SDF (14%) SE (9%) SP (5%)	Main focus: high-level programming languages, compilers; problem decomposition; flow of control: block,iteration, conditional; variables; data structure; error checking. Supporting concepts: statements, source code, translator, sensors, actuators, goal decomposition, top-down design, pseudocode, compound statement, assignment statement, parameters, primitives, syntax, domain, beacon, data flow, recursion.
Ch. 6. Operating Systems: Working Together	11%	OS (5%) SF (9%) IM (3%) IAS (3%)	Main focus: policy; resources and processes; protection; scheduling policies; memory management; message passing, decoupling; file systems. Supporting concepts: kernel, time quantum, multitasking, thread of execution, context switch, least privilege, privileged mode, user mode, system calls, round-robin policy, first-come first-served policy, priority-based policy, shortest remaining time policy, CPU utilization, throughput, latency, fairness, physical address, logical address, memory fragmentation, frames, paging, demand paging, virtual memory, socket, multiple threads.
Ch. 7. Computer Networks: Making Connections	9%	NC (3%) SF (9%) IAS (3%)	Main focus: hypertext; the Internet, Internet design principles; protocols, layers of services; packet switching; security. Supporting concepts: memex, associative indexing, client-server model, infrastructure, end-to-end protocol, packet, connectionless, host, global addressing, open architecture, processing on the edges of the Internet, routers, no global controller, “best effort” delivery, Internet Protocol Suite, link layer, network layer, Internet layer, transport layer, application layer, phishing, virus.
Ch. 8. Theoretical Computer Science: Pushing Boundaries	12%	AL (9%) DS (13%)	Main focus: finite state machines; Turing machines, the Church-Turing thesis, undecidability; time complexity, tractability, P, NP. Supporting concepts: states, transitions, pigeonhole principle, halting problem, linear, quadratic, polynomial, exponential, rate of growth, worst-case performance, efficiency, subset sum problem, factorial, traveling salesperson problem, reduction, NP-complete.
Ch. 9. Artificial Intelligence: Being Smart	12%	IS (3%) DS (13%) CN (1%)	Main focus: environments and agents; classical AI, physical symbol system hypothesis; search, theorem proving, machine learning, optimization. Supporting concepts: task environment, static environment, deterministic environment, observable environment, sensors, actuators, simple reflex agent, stimulus-response agent, model-based reflex agent, goal-based agent, utility-based agent, symbols, symbol structures, physical symbol system, problem representation, search frontier, uniform cost search, A* search, propositional logic, proposition, complement, clause, knowledge base, truth-preserving, resolution rule, logical equivalence, truth table, resolution theorem proving, decision tree, objective function, hill climbing, satisficing, computational science.
Ch. 10. Human-Computer Interaction: Thinking About People	8%	HC (2%) SP (5%)	Main focus: usability (effectiveness, efficiency, user satisfaction); design rules; human-centered computing; principles for design. Supporting concepts: “new users should find clear directions,” “expert users should have efficient shortcuts,” “it should be easier to do the right thing than the wrong thing,” “it should be just as easy to recover from mistakes as it is to make them in the first place,” interactive computing, command line interface, direct manipulation, embodied interaction, “focus on users from the start,” “test the system with users as it’s being built,” iterative design.

A different way to see the connections between Ordinary Mortals and the ACM’s view of computer science is to consider the CC2001 Computer Science volume, Final Report, which contains as an appendix a proposal for a “breadth-first” introductory course in computer science. The proposal is for a course called “CS100B. Preview of Computer Science”, described as below. In the syllabus suggested by the ACM, I’ve marked in red those topics not covered in Ordinary Mortals and inserted a few comments in italics about topics included in Ordinary Mortals but not in the syllabus.

Offers a broad overview of computer science designed to provide students with an appreciation for and an understanding of the many different aspects of computer science. Topics include discrete mathematics, an introduction to programming languages, algorithmic problem solving, analysis of algorithmic complexity, basic concepts in hardware, operating systems, networks, graphics, and an overview of the social context of computing. No background in computer science is assumed or expected. The course is intended for both students who expect to major or minor in computer science as well as for those not planning on taking additional course work.

Syllabus:

• Mathematical preliminaries: Sets, functions, logic, proofs (but with no formal rigor)
• Algorithms (and abstract data types): Definition, design, and implementation; introduction to classical algorithms (sorting, searching, spanning trees, and pattern matching); sequences, trees, and graphs
• Algorithmic analysis: Efficiency; asymptotic analysis; computational complexity; big-O notation; polynomial vs. exponential growth; computability
• Hardware realizations of algorithms: Data representation (only in the abstract, as encoding); the von Neumann model of computation; the fetch/decode/execute cycle; basic machine organization
• Programming fundamentals: Overview of programming fundamentals and object- oriented design principles; brief introduction to a programming language that supports the object-oriented paradigm
• Operating systems and virtual machines: Historical evolution of operating systems; responsibilities of an operating system; basic components of an operating system
• Networking and computer graphics (graphics in sidebar only): Brief introduction to some of the basic concepts in networking and computer graphics
• Artificial intelligence: Overview of agents, environments, and search; brief introduction to theorem proving, machine learning, and optimization
• Human-computer interaction: Usability and design principles
• Social and professional issues: Social context of computing; responsibilities of computing professionals

Ordinary Mortals and CS Principles
Computer Science: Principles is a proposed Advanced Placement course for high school students. A "Claims and Evidence" document identifies 26 key concepts in the course. Ordinary Mortals covers most but not all of them; again, the level of detail in the book is not equivalent to a real course. Mapping the concepts to book chapters would be a large undertaking; the list below gives a rough idea about where specific concepts are mentioned, with bold text indicating major themes in specific chapters.

Key Concept I.A. Innovations enabled by computing significantly affect communication, cognition, and human interaction.
Ch. 1 (NLS, WWW, brief mention of cognitive science); Ch. 7 (mail and email); Ch. 9 (solving problems with AI); Ch. 10 (human-computer interaction).

Key Concept I.B. Innovations enabled by computing lead to the creation of new artifacts that affect humanity in diverse ways.
Ch. 1 (graphical interfaces, CSCW, the Web); Ch. 5 (programming a robot); Ch. 7; Ch. 9; Ch. 10 (interactive computing).

Key Concept I.C. Innovations enabled by computing raise legal and ethical concerns.
(Note: Ethics is not covered; legal concerns are touched on only implicitly.)
Ch. 5; Ch. 6; Ch. 7 (network security in sidebar); Ch. 10.

Key Concept I.D. Computing is situated within economic, social, and cultural contexts.
Ch. 5; Ch. 8; Ch. 10.

Key Concept II.A. Computational systems and problems are developed, analyzed, and solved using multiple levels of abstraction.
Ch. 1; Ch. 2 (modularity as an aid to abstraction); Ch. 4 (encapsulating algorithms and data); Ch. 5 (problem decomposition); Ch. 6; Ch. 7; Ch. 9.

Key Concept II.B. Models and simulations use abstraction to raise and answer questions about real or imagined worlds.
Ch. 1; Ch. 2; Ch. 6; Ch. 7; Ch. 9.
(Note: Computational simulations are discussed explicitly only in a sidebar in Chapter 9. Informal models, i.e. detailed analogies to real-world processes, are present throughout.)

Key Concept III.A. People use computer programs to process information to gain insight and knowledge.
Ch. 1; Ch. 4 (e.g., semantic networks, small-world networks); Ch. 9.

Key Concept III.B. All digital data is represented using a combination of abstractions built upon finite binary sequences.
Ch. 2 (from the Jaquard loom to the Analytical Engine; encoding of data and instructions); Ch. 5; Ch. 7; Ch. 8; Ch. 9.
(Note: Bit-level representation is discussed only in a sidebar about number bases. The term “bit” is not defined in the book; it’s subsumed by the abstraction of encoding. Similarly, “digital” systems are described only as discrete systems.)

Key Concept III.C. Information must be translated into a digital format to be manipulated computationally.
Ch. 2; Ch. 3; Ch. 4; Ch. 5; Ch. 9; Ch. 10.
(Note: This is mostly implicit in connecting real-world activities to computation.)


Key Concept III.D. Computational manipulation of information requires consideration of representation, storage, security, and transmission.
Ch. 1 (Denning's Great Principles); Ch. 2 (the storage hierarchy); Ch. 3; Ch. 4 (structured data); Ch. 5; Ch. 6; Ch. 7 (networking); Ch. 8; Ch. 10.

Key Concept IV.A. A computational algorithm is a precise sequence of instructions for a process that can be executed by a computer.
Ch. 1; Ch. 2; Ch. 3 (CPU instructions); Ch. 4 (algorithms); Ch. 5 (programs); Ch. 8; Ch. 9.

Key Concept IV.B. Algorithms are expressed using languages.
Ch. 4; Ch. 5 (translating between abstract algorithms and a programming language).
(Note: Discussion of formal languages is not explicit in the book; it would fit most naturally in Chapter 8, on theoretical computer science.)

Key Concept IV.C. Computational problems can be categorized by their complexity.
Ch. 8 (time complexity, tractability); Ch. 9.

Key Concept IV.D. Algorithms are evaluated analytically and empirically.
Ch. 4; Ch. 5; Ch. 7; Ch. 8 (time complexity, computability); Ch. 9.

Key Concept V.A. Translating human intention into a computational artifact is part of programming.
Ch. 5 (requirements and programming); Ch. 6; Ch. 10.

Key Concept V.B. Programs are developed and used by people.
Ch. 1; Ch. 5 (programming); Ch. 6; Ch. 10 (HCI).

Key Concept V.C. Programming uses mathematical and logical concepts.
Ch. 2; Ch. 4; Ch. 5; Ch. 8 (e.g., the halting problem); Ch. 9 (e.g., resolution theorem proving).
(Note: Mathematics and logic are downplayed throughout the book, except in Chapters 8 and 9.)

Key Concept V.D. Modularity and parameterization are techniques for writing programs.
Ch. 2; Ch. 4; Ch. 5 (Python functions with variable parameters); Ch. 6 (processes and resources; process communication); Ch. 7 (protocols and levels of services); Ch. 10.

Key Concept VI.A. Networks connect computers, sub-networks, and other networks.
Ch. 7.

Key Concept VI.B. System development requires the application of appropriate design principles.
Ch. 2; Ch. 3 (e.g., architecture efficiency); Ch. 5 (e.g., modularity, abstraction); Ch. 6; Ch. 7; Ch. 10 (user-centered design).

Key Concept VI.C. Computer systems are composed of input, output, storage, and processing, their relations and interactions.
Ch. 2 (the Analytical Engine); Ch. 3 (the von Neumann architecture); Ch. 6; Ch. 10.

Key Concept VI.D. Characteristics of a system affect the applications for which it can be used.
Ch. 3; Ch. 5; Ch. 6; Ch. 7; Ch. 8; Ch. 9; Ch. 10 (the evolution of interactive computing).

Key Concept VII.A. Computing enables innovation by automating processes.
Ch. 2; Ch. 3; Ch. 4; Ch. 5; Ch. 7; Ch. 9 (AI); Ch. 10.

Key Concept VII.B. Computational modeling fosters innovation and knowledge.
Ch. 2; Ch. 4; Ch. 9.
(Note: Computational modeling is not treated in the book except in sidebars about graphics, Ch. 2, and about computational science, Ch. 9.)

Key Concept VII.C. Computational approaches and data analysis enable innovation.
Ch. 9; Ch. 10.
(Note: Data analysis is not treated in the book except in the limited context of counting operations in an algorithm, as part of a discussion of time complexity.)

Key Concept VII.D. Computing enables innovation by providing access to and sharing of information.
Ch. 1; Ch. 3; Ch. 7; Ch. 10.