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

 

 




Navigate to Supplementary Material Below

 




 

 

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.

Top

 

 

Complementary Problem Sets for Part II

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:


Top

 

 

Book's Preface

Why a book on CS0 from scratch?

Most of us write the books that we would have wanted to read and this is no different. As such, it follows a normal CS0 breadth-first approach but lays particular emphasis on computational thinking and related topics in data science.

My hope is this book will help build a theoretical and practical foundation for learning computer science from the ground up. It's not quite from first principles as this is not a rigorous text. But, following William of Occam's Razor, it is placed on a firm mathematical footing that starts with the fewest assumptions.

And so we delve into defining elementary ideas like data and information; along the way, we quantify these ideas and eke out some of their links to fundamental physics in an effort to show the connection between computer science and the universe itself. In fact, all the laws of physics can be represented as computable functions, and we can, in a very real sense, think of computer science as the most basic representation of the physical universe.

The eminent physicist John A. Wheeler went so far as to say, ". . . the universe is made of information; matter and energy are only incidental." I view the role of this book, at its theoretical core, to be to help explore, elucidate, and communicate this deep and perhaps surprising relationship between physics, information, and computation.

Target Audience

This book would be most appropriate for highly-motivated undergraduates who have a significant technical bent and a genuine interest in computer science. It is also appropriate for non-CS graduate students or non-CS professionals who are interested in learning more about computer science and programming for either professional or personal development.

So what kind of a background do you need to appreciate these various connections and learn some of this advanced material? Although you should be quantitatively inclined, you don't need any specific background in mathematics. Whatever math we need, we'll derive or explain along the way. Things might look heinous at times but all the tools you need should be in here.

Book Organization

Computer science is a diverse field and, in Part 1, we explore some of its theoretical bases in a connected but wide-ranging manner with an emphasis on breadth, not depth. Some chapters might still pack quite a punch but, if students are interested in computer science, they should get an overview of the field in large measure, not necessarily in its entirety. Not only is computer science an enormously broad area but this book, to paraphrase Thoreau, is limited by the narrowness of my experience and vision to those areas that caught my eye.

For that matter, this book is not a comprehensive introduction to a particular programming language, either. By necessity, we are constrained to only meeting those parts of Python or Java that support our understanding of fundamental computational ideas. In general, computer scientists tend to be a language agnostic bunch who pick the most appropriate language for a particular problem and that's the approach in this book, as well. But we should still get a sense of the large variety of topics that underly our study of computer science, from the abstract mathematical bases to the physical underpinnings.

Once the theoretical foundation is laid in Part 1, we shift gears to a purely pragmatic exploration of computing principles. Computer science is an inherently empirical science; in computer science, we have the unique opportunity to be able to explore highly theoretical content grounded in a pragmatic framework. By allowing students to actually implement and execute theoretical ideas, we can give them an opportunity few sciences can offer: the immediate testing of ideas they have learned or developed from a textbook or from their own research.

So, in Part 2, we learn the basics of computation and how to actually use our greatest tool: programming. These chapters should be short and approachable; students will hopefully find these digestible in short sittings so they can immediately apply all the ideas they've learned to start writing substantial programs, or computational solutions, in short order.

In Part 3, we'll explore some relatively sophisticated computational ideas. We'll both meet powerful programming concepts as well as investigate the limits of computational problem solving including examination of P vs. NP and Big O notation. We'll also increase the tools in our toolkit by learning about Object-Oriented Programming, GUI development, machine learning, data science, and some of the underlying principles of software engineering used in industry.

How to use this book

Depending on student or instructor interests, Part 1 can be considered completely optional and skipped in its entirety. The most important aspects of Part 1 are summarized in Ch. 3 and, if you don't want to emphasize the theoretical underpinnings, you can safely choose to start directly with Part 2. Similarly, in Part 3, you can pick and choose any chapters that interest you as each chapter in Part 3 is independent of the other chapters. For a typical semester-length course, I spend about 1-2 weeks on Part 1, cover all of Part 2, and pick topics of interest from Part 3 depending on the interests of the class.

Nota Bene: This book uses standard bibliographical notation as is common in computer science literature so references are indicated by a number in brackets, like [XX]. It also uses bold and italics to define phrases and emphasize concepts inline. Finally, it contains call out boxes like IDEA boxes, NOTE boxes, etc., which are important points that should be highlighted separately or extend a concept without breaking the main narrative.1

Okay, that's enough build-up... strap yourself in and let's get started on our adventure!

1The same applies to footnotes, of course.

Top

 

 

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. Thinking about 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: Imperative Programming

  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

Top

 

 

Text Preview

Please feel free to download the first three chapters here.

Top

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.

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