Essential Computational Thinking
Essential Computational Thinking: Computer Science from Scratch (Preliminary Edition) is published and distributed by Cognella, Inc. Please feel free to download the first three chapters here.
Essential Computational Thinking
Computer Science from Scratch
by Ricky J. Sethi
Video Series to Complement Part I
Video series to complement Ch. 0  2 of Essential Computational Thinking:
 Ch. 0: On The Road to Computation
 Ch. 1: Computational Thinking and Information Theory
 Ch. 2: Computational Problem Solving
This excellent video series is created by Brit Cruise and Art of the Problem.
AutoGraded Problem Sets to Complement Part II
Autograded problem sets for Ch. 3  7 of Essential Computational Thinking can be found on Snakify's Lessons 1  11. In particular, please use the following guide:
 Ch. 3: Computational Thinking and Structured Programming
 Lesson 1: Input, print and numbers
 Ch. 4: Data Types and Variables
 Lesson 2: Integer and float numbers
 Ch. 5: Control Structures
 Lesson 3: Conditions: if, then, else
 Lesson 4: For loop with range
 Lesson 6: While loop
 Ch. 6: Data Structures
 Lesson 5: Strings
 Lesson 7: Lists
 Lesson 9: Twodimensional lists (arrays)
 Lesson 10: Sets
 Lesson 11: Dictionaries
 Ch. 7: Procedural Programming
 Lesson 8: Functions and recursion
Book's Table of Contents
Part I: Theory: What is Computer Science?

On The Road to Computation
 What is Knowledge?
 Declarative vs Imperative Knowledge
 The Key to Science
 Computer Science: The Study of Computation
 A Review of Functions
 Computable Functions
 Talking in Tongues: Programming Languages

Computational Thinking and Information Theory
 What is Thinking?
 Deductive vs Inductive Thinking
 Thinking About Probabilities
 Logical Thinking
 Computational Thinking and Computational Solutions
 Two Fundamental Models of Programming
 Pseudocode
 Functional and Imperative Models of Computation
 Information Theory
 Shannon's Information Entropy

Computational Problem Solving
 What is a Model?
 Data Representations
 Number Representations
 Digital Representations
 Boolean Algebra
 What is Information Processing?
 What is Computer Information Systems (CIS)?
 Programming Languages
 Computational Thinking
 Problem Space and System State
 Computational Thinking in Action

Computational Thinking and Structured Programming
 Review of Computation
 Computational Thinking Basics
 Minimal Instruction Set
 Getting Started with Python
 Syntax, Semantic, or Logic Errors
 State of a Computational System
 Natural vs Formal Languages
 Translating your programs
 Playing with Python
 An example using Computational Thinking

Data Types and Variables
 Data = Values + Operations
 Different Types of Data
 Variables and Expressions
 Input/Output
 An Example Using Computational Thinking

Control Structures
 Algorithms and Control Structures
 Sequence
 Selection
 Repetition
 An Example Using Computational Thinking

Data Structures
 Abstract Data Types
 A NonTechnical Abstract Type
 Advantages of ADTs
 Data Structures
 Strings
 Lists and Tuples
 An Example Using Computational Thinking

Procedural Programming
 Functions Redux
 Functions in Python
 Subroutines with parameters and values
 Namespaces and Variable Scope
 Exception Handling
 File I/O
 An Example Using Computational Thinking

ObjectOriented Programming
 OOPs!... A History Again
 Objects and ObjectOriented Programming
 Introduction to Java
 Data Abstraction and Information Hiding
 Encapsulation and Composition
 Inheritance
 Polymorphism
 Data Structures in Java
 File I/O and Exception Handling in Java
 An Example Using Computational Thinking

Computational Complexity
 Big O Notation
 Searching and Sorting Algorithms
 P vs NP

Databases and MDM
 Master Data Management
 Data Modeling and SQL
 Relational Database Components and Normalization

Data Science
 Business Informatics and Data Analysis
 Data Science
 Machine Learning
Part II: Basics: Algorithmic Expression
Part III: Advanced: Data and Computation (not in Preliminary Edition)
Bibliography
Index
Some Key Images
Caption: Some essential ideas in the theory of computation: an effective procedure is a finite set of instructions for carrying out some unambiguous symbolic manipulation or transformation. If an effective procedure can calculate all the values of a function, it is called an algorithm for that function and that function is then considered a computable function. A Turing Machine is a mathematical description of any algorithm in terms of a hypothetical machine with a simple readwrite head and a tape of paper; a Turing Machine is one formalization of the general idea of an algorithm. In fact, computation itself can then be thought of as the study of algorithms or such formal models of algorithms.
Caption: Computational Thinking is a set of techniques for solving complex problems that can be classified into three steps: Problem Specification, Algorithmic Expression, and Solution Implementation & Evaluation. The skills involved in each step of the Computational Thinking Approach are:
 Problem Specification, which involves Abstraction, Decomposition, and Pattern Recognition
 Algorithmic Expression, which involves Algorithm Design
 Solution Implementation & Evaluation, which involves testing and Generalization
Caption: Data → Information → Knowledge
Fundamental science is about making falsifiable predictions that are verified by experiment. We start with observations of nature; giving these raw facts some structure transforms values into data.Then, giving some context to that data, or reaching some conclusion with that data, gives us information. That information reflects our prediction about the world.
In Shannon's Information framework, data can be thought of as an organized sequence of symbols representing ideas or observations where the symbols might have some value, which is some meaning in some interpretation. If the context that transforms data into information is the probability of occurrence of the messages or the symbols that constitute the messages, we end up with Shannon’s Information measure. We can then transform one representation of data to another as Shannon's Information framework allows us to encode any message into binary digits with no loss of information as long as the probabilities, or frequencies, of the symbols remains the same.
Information, in this framework, is a property of a message that is intended to be communicated between a system consisting of a sender and a receiver. It is an abstract idea that is encoded into some carrier and that reflects some measure of uncertainty about the system. Information is thus data that has some context which helps resolve uncertainty or answers a question of some sort and so reflects our prediction about the world. The fundamental unit of this kind of information, the bit, can be thought of as the fundamental element of communication.
More generally, we can organize information into a knowledge base, a repository of interlinked entities organized using a semantic model with constraint rules, and then use some logicbased reasoning to derive a decision about the future, which is our actionable knowledge that we can subsequently falsify. Knowledge is thus an implicit (practical, knowhow skills) or explicit (theoretical, knowwhat facts) understanding of formalized, organized information that can help solve some problem.
Computation is the process by which we transform data into information and then into knowledge. Computable, in this context, means that such transformations can be carried out by a Universal Turing Machine. A Turing machine consists of certain processes, or effective procedures, in mathematics that could be carried out by following a set of rules.
Computation using these bits of information, it turns out, is related to physical entropy in thermodynamics and statistical mechanics. Entropy, in the physical sense, can be thought of as the ability to exchange, or transform, work and heat energy and is something that increases in spontaneous transformations, as encapsulated in the Second Law of Thermodynamics.
Energy is the ability to do work and work, in turn, can be thought of as a Force times a Displacement of some sort; e.g., in mechanical work, it’s mechanical force times mechanical displacement. Since entropy is so fundamental in the universe, we can say the universe itself is informational at its most elementary level and we can then think of the universe as being computational at this basic level.
Caption: An Informal Model of Fundamental Program Elements: most programs consist of elements like literals, variables, functions, objects, and classes. Program statements are made up of expressions which contain elements. In addition, programs utilize control structures to determine the flow of execution, the order in which statements are executed. Three fundamental control structures, sequence, selection, and repetition, are sufficient to specify any programmatic solution. These control structures are implemented as statements; e.g., the selection control structure is implemented using the if
statement in most programming languages.
Caption: Different Kinds of Errors: Syntax, Semantic, and Logical errors occur at either compiletime (syntax and static semantic) or runtime (dynamic semantic and logical). Semantic and logical errors are also sometimes referred to as exceptions and we can use exception handling to take care of such exceptional situations. Most languages use exceptions for both compiletime and runtime errors. In languages like Java, exceptions that occur at compiletime are called checked exceptions whereas runtime exceptions are called unchecked exceptions. In languages like Python, C++, and C#, the compiler does not force the programmer to deal with exceptions so all exceptions are unchecked.
Caption:
Data Types and Representations:
Values can be described as the quantifiable observations, the raw facts, of any aspect of the physical world like things, events, or even ideas. Giving these values some structure converts them to data, where we often use symbols to represent these values or groups of values at a higher level of abstraction. Data representation refers to the particular structure, or form, of the values used to help facilitate the processing, storage, or transmission of those values.
Data can broadly be represented as numeric data, which consists of numbers that can be utilized in mathematical operations, and character data, where letters, numerals, and symbols in ordered sequences are used to represent strings that are not used in mathematical calculations. The kind of data, or its category as Aristotle might have said, is its type. Different types of data have different characteristics.
A data model is a collection of concepts for describing data that tells us how data is organized and represented. More formally, it is an abstract model that organizes how data is represented and how the data elements relate to each other. A type is the collection of values and a data type consists of the type along with the operations permitted to manipulate that type. A data type can also be thought of as a logical, languageindependent expression of a data model and the associated operations that are valid on those data values, independent of any particular language.
The data type thus tells us both the kinds of values that data can represent as well as the kinds of operations allowed on those values. An abstract data type (ADT) is a data type that does not specify the details of how data will be organized in memory or which specific algorithms will be used for carrying out the operations on those data values. ADTs specify what operations can be performed on the data values but not how those operations will actually be implemented. While an ADT is the logical specification of a data type in some particular language but without the implementation details, a data structure is the actual implementation of that ADT in that particular language.
A variable is the name for a stored value that represents some fundamental characteristic of the system or function. More abstractly, a variable is any symbol used to represent an unspecified element chosen from some set of elements. These values and variables can be combined in expressions and those expressions combined further into statements, the instructions which make up an algorithm.
^{1}Some might distinguish between an ADT Specification, which is more mathematical and languageindependent, and is similar to a data type definition without any implementation details; an ADT Interface, which is languagedependent but still does not contain any implementation details and might be represented by a class or an abstract class in C++ or an interface class in Java; or a Concrete Data Type, which is languagedependent and includes the actual implementation of the ADT in that particular language.
Caption:
Confusion Tables:
Confusion matrix with True Positive, True Negative, False Positive, and False Negative classifications. In a Hypothesis Testing framework, the null hypothesis, the statement we want to falsify, usually indicates there is no real effect. A false positive (α) is incorrectly rejecting the null hypothesis while a false negative (β) is incorrectly accepting the null hypothesis. Alpha, α, is the significance level used in Hypothesis Testing and Beta, β, is used to determine the statistical power of a study, which is the probability that it rejects a false negative, 1  β.
Caption:
Eight Common ML Approaches:
Pragmatically speaking, there are usually eight kinds of questions
we answer in most data analytic applications. Each of these eight
questions is usually addressed using a different machine learning
algorithm. These eight common questions and their corresponding
approaches are:
 Find if there are any unusual data points: is this weird? → Anomaly Detection
 Discover how this is organized or structured? → Clustering and Dimensionality Reduction
 Predict a number, like how much or how many? → Regression
 Predict if something is A or B? → Classification
 Predict if this is A or B or C or ...? → MultiClass Classification
 Find the best way to make your next move; what should you do next? → Reinforcement Learning
 Is the data supercomplicated and hard to understand? → Deep Learning
 Is accuracy quality really important? → Ensemble Methods
Caption: General Machine Learning approach:
 Start by picking a learning algorithm that's appropriate for the task at hand
 Use the Training Dataset to learn the algorithm's parameter values
 Use the Validation Dataset to tune the algorithm's hyperparameters and architecture — the resulting algorithm is the tentative model
 Use the Testing Dataset to gauge the tentative model's performance and, if no changes are needed, this is the final model
 Now you can apply the final model to unseen data to make your final prediction for that task
Profile

 Nota Bene: This picture is from my wedding many years (and even more pounds) ago. I don't look like this anymore but I've learned in life that, once you find a good picture, you hang on to it forever!
Ricky J. Sethi is currently an Associate Professor of Computer Science at Fitchburg State University, Director of Research for The Madsci Network, and Team Lead for SNHU Online.
Curriculum Vitae (CV)
Please feel free to download my Curriculum Vitae (PDF).
Profile Summary
 Affiliations:
 Fitchburg State University
 The Madsci Network
 Southern New Hampshire University
 Education:
 University of California, Berkeley
 University of Southern California
 University of California, Riverside
 Field of Research:
 Computer Vision/Multimedia
Group analysis in video using physicsbased, machine learning models  Social Computing
Virtual communities & group collaboration for science learning  Data Science
Multimedia analysis and reproducibility via semantic workflows
 Computer Vision/Multimedia