Computational Thinking: A Perspective on Computer Science

✍ Scribed by Zhiwei Xu, Jialin Zhang

• Publisher: Springer
• Year: 2021
• Tongue: English
• Leaves: 338
• Category: Library

✦ Synopsis

This textbook is intended as a textbook for one-semester, introductory computer science courses aimed at undergraduate students from all disciplines. Self-contained and with no prerequisites, it focuses on elementary knowledge and thinking models. The content has been tested in university classrooms for over six years, and has been used in summer schools to train university and high-school teachers on teaching introductory computer science courses using computational thinking.

This book introduces computer science from a computational thinking perspective. In computer science the way of thinking is characterized by three external and eight internal features, including automatic execution, bit-accuracy and abstraction. The book is divided into chapters on logic thinking, algorithmic thinking, systems thinking, and network thinking. It also covers societal impact and responsible computing material – from ICT industry to digital economy, from the wonder of exponentiation to wonder of cyberspace, and from code of conduct to best practices for independent work.

The book’s structure encourages active, hands-on learning using the pedagogic tool Bloom's taxonomy to create computational solutions to over 200 problems of varying difficulty. Students solve problems using a combination of thought experiment, programming, and written methods. Only 300 lines of code in total are required to solve most programming problems in this book.

✦ Table of Contents

Preface
Introduction
Problem-Solving Examples
Intended Audience
Structure of Contents
How to Use This Book?
Notations
Supplementary Material
Acknowledgments
Bibliographic Notes
References
Contents
Chapter 1: Overview of Computer Science
1.1 Computational Processes in Problem Solving
1.2 Characteristics of Computational Thinking
1.2.1 The Three Features Without
1.2.2 The Eight Understandings Within
1.2.3 A Research Viewpoint of Computer Science
1.3 Relation of Computer Science to Society
1.3.1 Computer Science Supports Information Society
1.3.2 Computer Science Shows Three Wonders
1.3.3 Computer Science Has Three Persuasions
1.3.4 Computational Thinking Is a Symphony
1.4 Exercises
1.5 Bibliographic Notes
References
Chapter 2: Processes of Digital Symbol Manipulation
2.1 Data as Symbols
2.1.1 Conversions Between Binary and Decimal Number Representations
2.1.2 Representing Integers in Two´s Complement Representation
2.1.3 Representing English Characters: The ASCII Characters
2.2 Programs as Symbols
2.2.1 A Number of Simple Programs
2.2.2 Programs Relating Character Strings to Integers
2.2.3 Good Programming Practices
2.2.4 Using Dynamic Programing to Compute Fibonacci Number F(50)
2.3 Computer as a Symbol-Manipulation System
2.3.1 A Glimpse Inside a Computer
2.3.2 A Step-By-Step Process on a von Neumann Computer
2.4 Exercises
2.5 Bibliographic Notes
References
Chapter 3: Logic Thinking
3.1 Boolean Logic
3.1.1 Propositional Logic
3.1.1.1 Propositions and Logic Connectives
3.1.1.2 Truth Table
3.1.1.3 Properties of Logic Connectives
3.1.1.4 Boolean Expression and Boolean Function
3.1.1.5 Normal Forms
3.1.1.6 The Number of Boolean functions
3.1.1.7 () Kleene Logic
3.1.1.8 Using Propositional Logic to Solve Problems
3.1.2 Predicative Logic
3.1.2.1 Predicate and Quantifier
3.1.2.2 More Examples of Writing Predicative Logic Expressions
3.1.2.3 Inference Rules and Axiomatic Systems in Boolean Logic
3.2 Automata and Turing Machines
3.2.1 Mechanical Theorem Proving
3.2.2 Automata
3.2.3 Computation on Turing Machine
3.2.3.1 Notable Details of Turing Machine
3.3 Power and Limitation of Computing
3.3.1 Church-Turing Hypothesis
3.3.2 () Incomputable Problems and Paradoxes
3.3.3 () Gödel´s Incompleteness Theorems
3.4 Exercises
3.5 Bibliographic Notes
References
Chapter 4: Algorithmic Thinking
4.1 What Are Algorithms
4.1.1 Knuth´s Characterization of Algorithm
4.1.2 The Sorting Problem and the Bubble Sort Algorithm
4.1.3 Asymptotic Notations
4.2 Divide-and-Conquer Algorithms
4.2.1 The Insertion Sort Algorithm
4.2.2 The Merge Sort Algorithm
4.2.3 Single Factor Optimization
4.2.4 Integer Multiplication
4.2.5 Matrix Multiplication
4.2.6 Summarization
4.3 Other Examples of Interesting Algorithms
4.3.1 Dynamic Programming
4.3.2 () The Greedy Strategy
4.3.3 The Randomization Strategy
4.3.4 () Search Algorithms
4.3.4.1 Linear Search in O(n) Time
4.3.4.2 Binary Search in O(logn) Time
4.3.4.3 Hash Search in O(1) Time
4.4 P vs. NP
4.4.1 Time Complexity
4.4.2 P and NP
4.4.3 () Examples in the NP Class
4.5 Exercises
4.6 Bibliographic Notes
References
Chapter 5: Systems Thinking
5.1 Systems Thinking Has Three Objectives
5.1.1 Being Thorough
5.1.2 Being Systematic
5.1.3 Coping with Complexity
5.2 Abstraction
5.2.1 Three Properties of Abstraction: COG
5.2.2 Data Abstractions
5.2.2.1 Positional Notation of Number Systems
5.2.2.2 Representing Real Numbers
5.2.2.3 Test If Two Floating-Point Numbers Are Equal
5.2.2.4 ASCII, Unicode, and UTF-8
5.2.2.5 Review of Bit, Byte, Character, Integer, Array, and Slice
5.2.2.6 Pointers and Addressing Modes
5.2.2.7 The File Abstraction
5.2.3 Control Abstractions
5.3 Modularization
5.3.1 Combinational Circuits
5.3.1.1 Various Adders
5.3.2 Sequential Circuits
5.3.2.1 Various Types of Memory Cells
5.3.2.2 A Logic Circuit with Feedbacks: The Delay Flip-Flop
5.3.2.3 A General Organization of Sequential Circuits
5.3.2.4 Serial Adder and Subtractor
5.3.3 Instruction Set and Instruction Pipeline
5.3.4 Software Stack on a von Neumann Computer
5.4 Seamless Transition
5.4.1 Yang´s Cycle Principle
5.4.2 Postel´s Robustness Principle
5.4.3 von Neumann´s Exhaustiveness Principle
5.4.4 (***) Amdahl´s Law
5.4.4.1 Instruction Pipeline Revisited
5.4.4.2 Cache
5.4.4.3 Parallel Computing
5.5 Exercises
5.6 Bibliographic Notes
References
Chapter 6: Network Thinking
6.1 Network Terms
6.2 Connectivity
6.2.1 Naming
6.2.1.1 The Namespaces of the Internet: Domain Names vs. IP Addresses
6.2.1.2 The Namespace of the World Wide Web: URL
6.2.2 Network Topology
6.3 Protocol Stack
6.3.1 The Web over Internet Stack
6.3.1.1 How Does the Protocol Stack Work? Fetch a Home Page from a Server
6.3.2 Elementary Web Programming
6.3.2.1 Create a Web Server and Static Webpages
6.3.2.2 Create a Dynamic Webpage
6.4 Network Laws and Responsible Computing
6.4.1 Bandwidth, Latency, and User Experience
6.4.1.1 Bandwidth and Latency: Extreme and User-Experienced Values
6.4.1.2 Data Compression: Lossless and Lossy Compressions
6.4.2 Network Effect
6.4.2.1 Metcalfe´s Law and Reed´s Law
6.4.2.2 The Viral Marketing Phenomenon
6.4.3 Responsible Computing
6.4.3.1 Cybersecurity Issues
6.4.3.2 Privacy Awareness
6.4.3.3 Respecting Professional Norms
6.5 Exercises
6.6 Bibliographic Notes
References
Chapter 7: Projects
7.1 Turing Adder: Turing Machine for Serial Additions
7.2 Text Hider: Program to Hide Text in Picture
7.3 Human Sorter: Team Computer for Quicksort
7.4 Personal Artifact: Web Page of Creative Expression
Chapter 8: Appendices
8.1 Multiples and Fractions
8.2 Programming Basics
8.3 Pointers to Supplementary Material
Index