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:

This excellent video series is created by Brit Cruise and Art of the Problem.


 

 

Auto-Graded Problem Sets to Complement Part II

Auto-graded 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:



 

 

Book's Table of Contents

Part I: Theory: What is Computer Science?

  1. On The Road to Computation
    1. What is Knowledge?
    2. Declarative vs Imperative Knowledge
    3. The Key to Science
    4. Computer Science: The Study of Computation
    5. A Review of Functions
    6. Computable Functions
    7. Talking in Tongues: Programming Languages
  2. Computational Thinking and Information Theory
    1. What is Thinking?
    2. Deductive vs Inductive Thinking
    3. Thinking About Probabilities
    4. Logical Thinking
    5. Computational Thinking and Computational Solutions
    6. Two Fundamental Models of Programming
    7. Pseudocode
    8. Functional and Imperative Models of Computation
    9. Information Theory
    10. Shannon's Information Entropy
  3. Computational Problem Solving
    1. What is a Model?
    2. Data Representations
    3. Number Representations
    4. Digital Representations
    5. Boolean Algebra
    6. What is Information Processing?
    7. What is Computer Information Systems (CIS)?
    8. Programming Languages
    9. Computational Thinking
    10. Problem Space and System State
    11. Computational Thinking in Action
  4. Part II: Basics: Algorithmic Expression

  5. Computational Thinking and Structured Programming
    1. Review of Computation
    2. Computational Thinking Basics
    3. Minimal Instruction Set
    4. Getting Started with Python
    5. Syntax, Semantic, or Logic Errors
    6. State of a Computational System
    7. Natural vs Formal Languages
    8. Translating your programs
    9. Playing with Python
    10. An example using Computational Thinking
  6. Data Types and Variables
    1. Data = Values + Operations
    2. Different Types of Data
    3. Variables and Expressions
    4. Input/Output
    5. An Example Using Computational Thinking
  7. Control Structures
    1. Algorithms and Control Structures
    2. Sequence
    3. Selection
    4. Repetition
    5. An Example Using Computational Thinking
  8. Data Structures
    1. Abstract Data Types
    2. A Non-Technical Abstract Type
    3. Advantages of ADTs
    4. Data Structures
    5. Strings
    6. Lists and Tuples
    7. An Example Using Computational Thinking
  9. Procedural Programming
    1. Functions Redux
    2. Functions in Python
    3. Sub-routines with parameters and values
    4. Namespaces and Variable Scope
    5. Exception Handling
    6. File I/O
    7. An Example Using Computational Thinking
  10. Part III: Advanced: Data and Computation (not in Preliminary Edition)

  11. Object-Oriented Programming
    1. OOPs!... A History Again
    2. Objects and Object-Oriented Programming
    3. Introduction to Java
    4. Data Abstraction and Information Hiding
    5. Encapsulation and Composition
    6. Inheritance
    7. Polymorphism
    8. Data Structures in Java
    9. File I/O and Exception Handling in Java
    10. An Example Using Computational Thinking
  12. Computational Complexity
    1. Big O Notation
    2. Searching and Sorting Algorithms
    3. P vs NP
  13. Databases and MDM
    1. Master Data Management
    2. Data Modeling and SQL
    3. Relational Database Components and Normalization
  14. Data Science
    1. Business Informatics and Data Analysis
    2. Data Science
    3. Machine Learning

Bibliography
Index

Some Key Images




Essential Ideas in Computation

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 read-write 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.




Computational Thinking Steps

Caption: Computational Thinking Approach for Solving Problems: the skills involved in each step of the Computational Thinking Approach are:

  1. Problem Specification, which involves Abstraction, Decomposition, and Pattern Recognition
  2. Algorithmic Expression, which involves Algorithm Design
  3. Solution Implementation & Evaluation, which involves testing and Generalization




Syntax, Semantic, and Logical Errors

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 logic-based reasoning to derive a decision about the future, which is our actionable knowledge that we can subsequently falsify. Knowledge is thus an implicit (practical, know-how skills) or explicit (theoretical, know-what 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.




Syntax, Semantic, and Logical Errors

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.




Syntax, Semantic, and Logical Errors

Caption: Different Kinds of Errors: Syntax, Semantic, and Logical errors occur at either compile-time (syntax and static semantic) or run-time (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 compile-time and run-time errors. In languages like Java, exceptions that occur at compile-time are called checked exceptions whereas run-time 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.




Syntax, Semantic, and Logical Errors

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, language-independent 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.

1Some might distinguish between an ADT Specification, which is more mathematical and language-independent, and is similar to a data type definition without any implementation details; an ADT Interface, which is language-dependent 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 language-dependent and includes the actual implementation of the ADT in that particular language.




Confusion Tables

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 - β.




Eight Common ML Approaches

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:

  1. Find if there are any unusual data points: is this weird? → Anomaly Detection
  2. Discover how this is organized or structured? → Clustering and Dimensionality Reduction
  3. Predict a number, like how much or how many? → Regression
  4. Predict if something is A or B? → Classification
  5. Predict if this is A or B or C or ...? → Multi-Class Classification
  6. Find the best way to make your next move; what should you do next? → Reinforcement Learning
  7. Is the data super-complicated and hard to understand? → Deep Learning
  8. Is accuracy quality really important? → Ensemble Methods
There are also additional questions that are often asked like "Is this the best?", which can be answered using Optimization or some such approach.




General Machine Learning approach

Caption: General Machine Learning approach:

  1. Start by picking a learning algorithm that's appropriate for the task at hand
  2. Use the Training Dataset to learn the algorithm's parameter values
  3. Use the Validation Dataset to tune the algorithm's hyperparameters and architecture — the resulting algorithm is the tentative model
  4. Use the Testing Dataset to gauge the tentative model's performance and, if no changes are needed, this is the final model
  5. Now you can apply the final model to unseen data to make your final prediction for that task


Profile

Ricky J. Sethi

    • 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 physics-based, machine learning models
    • Social Computing
      Virtual communities & group collaboration for science learning
    • Data Science
      Multimedia analysis and reproducibility via semantic workflows