Introduction to Computing
Explorations in Language, Logic, and Machines
David
Evans
Computer science is the study of information processes. Computer scientists study how to describe, predict properties of, and efficiently implement information processes. This book introduces the most important ideas in computing. It focuses on how to describe information processes by defining procedures, how to analyze the costs required to carry out a procedure, and the fundamental limits of what can and cannot be computed mechanically.
(Note: if you are taking my Udacity cs101 course, you are certainly welcome and encouraged to read this book. But, be forewarned, that Chapters 2-10 of this book use a different programming language than the Python language we are using in Udacity cs101. The example programs in the Scheme language used here look quite different from Python code, although the core CS concepts are the same as those we are learning in the Udacity course. Chapters 11 and 12 of this book do use Python as the main programming language.)
Contents
Introduction
1.2 Measuring Computing Power (Information, Representing Data, Growth of Computing Power)
1.3 Science, Engineering, and the Liberal Arts
1.4 Summary and Roadmap
Exercises and solutions: PDF
Part I: Defining Procedures
2.2 Language Construction
2.3 Recursive Transition Networks
2.4 Replacement Grammars
2.5 Summary
Exercises and solutions: PDF
3.2 Programming Languages
3.3 Scheme
3.4 Expressions (Primitives, Application Expressions)
3.5 Definitions
3.6 Procedures (Making Procedures, Substitution Model of Evaluation)
3.7 Decisions
3.8 Evaluation Rules
3.9 Summary
Exercises and solutions: PDF
4.2 Composing Procedures (Procedures as Inputs and Outputs)
4.3 Recursive Problem Solving
4.4 Evaluating Recursive Applications
4.5 Developing Complex Programs (Printing. Tracing)
4.6 Summary
Exercises and solutions: PDF
Part II: Analyzing Procedures
6.2 Mechanizing Logic (Implementing Logic, Composing Operations, Arithmetic)
6.3 Modeling Computing (Turing Machines)
6.4 Summary
7.2 Orders of Growth (Big O, Omega, Theta)
7.3 Analyzing Procedures (Input Size, Running Time, Worst Case Input)
8.2 Searching (Unstructured Search, Binary Search, Indexed Search)
8.3 Summary
Part III: Improving Expressiveness
9.2 Impact of Mutation (Names, Places, Frames, and Environments; Evaluation Rules with State)
9.3 Mutable Pairs and Lists
9.4 Imperative Programming (List Mutators, Imperative Control Structures)
9.5 Summary
10.2 Inheritance (Implementing Subclasses, Overriding Methods)
10.3 Object-Oriented Programming
10.4 Summary
11.2 Parser
11.5 Summary
Part IV: The Limits of Computing
12.2 The Halting Problem
12.3 Universality
12.4 Proving Non-Computability
12.5 Summary
Previous versions: Spring 2010 Edition, Fall 2009 Edition, Spring 2009 Edition
|
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License. |