Zhiwei Xu and Jialin Zhang
Computational Thinking: A Perspective on Computer Science
Logo of the publisher
Zhiwei Xu
University of Chinese Academy of Sciences, Beijing, China
Jialin Zhang
University of Chinese Academy of Sciences, Beijing, China
ISBN 978-981-16-3847-3 e-ISBN 978-981-16-3848-0
https://doi.org/10.1007/978-981-16-3848-0
The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2021
This work is subject to copyright. All rights are solely and exclusively licensed by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This Springer imprint is published by the registered company Springer Nature Singapore Pte Ltd.
The registered company address is: 152 Beach Road, #21-01/04 Gateway East, Singapore 189721, Singapore
To Hao, for continuous inspiration and support
Zhiwei
To my husband and little son, with love
Jialin
Preface
This book provides an introduction to computer science from the computational thinking perspective. It explains the way of thinking in computer science through chapters of logic thinking, algorithmic thinking, systems thinking, and network thinking. It is purposely designed as a textbook for the first computer science course serving undergraduates from all disciplines.
The book focuses on elementary knowledge such that all material can be covered in a one-semester course of Introduction to Computer Science. It is designed for all students, assuming no prior programming experience. At the same time, students with prior programming experience should not find the course boring.
The book practices an active learning method, utilizing recent advice by Donald Knuth: The ultimate test of whether I understand something is if I can explain it to a computer. The book is designed to enable students to rise from the basement level of
remembering to the top level of
creating in Blooms taxonomy of education objectives. More than 200 hands-on exercises, thought experiments, and projects are included to encourage students to create. Examples of creative tasks include:
Design a Turing machine to do n-bit addition, where n could be arbitrarily large. This could be a students first design of an abstract computer .
Design a team computer to do quicksort. This could be a students first design of a real computer , including its instruction set and machine organization.
Develop a computer application (a steganography computer program) to hide a text file hamlet.txt in a picture file Autumn.bmp.
Design a smart algorithm and a program to compute Fibonacci numbers F(n), where n could be as large as one million or even one billion.
Create a dynamic webpage of creative expression for a Kitty Band, which can play a piece of music given an input string of music scores.
The material of the book has been used in the University of Chinese Academy of Sciences since 2014, serving a required course for freshmen from all schools. It was also used in summer schools organized by China Computer Federation, to train university and high-school instructors on teaching a Computer Fundamentals course utilizing computational thinking.
Supplementary material is provided at cs101.ucas.edu.cn .
Zhiwei Xu
Jialin Zhang
Beijing, China
October 2021
Introduction
This textbook is for a one-semester course of Introduction to Computer Science (e.g., CS101), targeting undergraduate students from all disciplines. It is a self-contained book with no prerequisites. The little prior knowledge and notations needed are explained along the way and summarized in Appendices.
The book is designed to introduce elementary knowledge of computer science and the fields way of thinking. It has the following four objectives and features:
Embodying computational thinking. The way of thinking in computer science is characterized by three features without and eight understandings within. Introductory bodies of knowledge are organized into chapters of logic thinking, algorithmic thinking, systems thinking, and network thinking.
Aiming at upper levels of Blooms taxonomy, with a significant portion of learning material going from remember to create, as shown in Fig.. The learning method uses Knuths Test: The ultimate test of whether I understand something is if I can explain it to a computer. More than 200 hands-on exercises and thought experiments are included to encourage students to create.
Focusing on elementary knowledge without dumbing down. An explicit goal is that all material should be coverable in one semester, for a class of hundreds of students of all disciplines, assuming no prior programming experiences. At the same time, experienced students should not find the course boring.
Learning from a decade of educational experience. We spent 4 years designing the course and 6 years teaching the material. The contents have gone through three major revisions. For instance, version 1 has no programming. Version 2 includes Go language programming contents. Version 3 (the current version) requires a student to write roughly 300 lines of Go code and 100 lines of Web code, where most students can learn Web programming by themselves.
Problem-Solving Examples
Computer science is a subject studying computational processes in problem-solving and creative expression. This textbook includes over 200 problems as examples, exercises, and hands-on projects. They provide a glimpse of how computers work and what kinds of problem-solving and creative expression are enabled by computer science and computational thinking.
The book shows how to solve such problems. In doing so, it introduces elementary knowledge on not only how to use a computer but also how to design a computer. We demonstrate that computer science is intellectually interesting, by heeding Donald Knuths advice: In most of life, you can bluff, but not with computers. We take special care to avoid underestimating the potentials of students and dumbing down the course material.