Introduction to Computing. Explorations in Language, Logic, and Machines

✍ Scribed by David Evans

• Year: 2011
• Tongue: English
• Leaves: 266
• Edition: August 19, 2011
• Category: Library

✦ Table of Contents

Computing
Processes, Procedures, and Computers
Measuring Computing Power
Information
Representing Data
Growth of Computing Power
Science, Engineering, and the Liberal Arts
Summary and Roadmap
Language
Surface Forms and Meanings
Language Construction
Recursive Transition Networks
Replacement Grammars
Summary
Programming
Problems with Natural Languages
Programming Languages
Scheme
Expressions
Primitives
Application Expressions
Definitions
Procedures
Making Procedures
Substitution Model of Evaluation
Decisions
Evaluation Rules
Summary
Problems and Procedures
Solving Problems
Composing Procedures
Procedures as Inputs and Outputs
Recursive Problem Solving
Evaluating Recursive Applications
Developing Complex Programs
Printing
Tracing
Summary
Data
Types
Pairs
Making Pairs
Triples to Octuples
Lists
List Procedures
Procedures that Examine Lists
Generic Accumulators
Procedures that Construct Lists
Lists of Lists
Data Abstraction
Summary of Part I
Machines
History of Computing Machines
Mechanizing Logic
Implementing Logic
Composing Operations
Arithmetic
Modeling Computing
Turing Machines
Summary
Cost
Empirical Measurements
Orders of Growth
Big O
Omega
Theta
Analyzing Procedures
Input Size
Running Time
Worst Case Input
Growth Rates
No Growth: Constant Time
Linear Growth
Quadratic Growth
Exponential Growth
Faster than Exponential Growth
Non-terminating Procedures
Summary
Sorting and Searching
Sorting
Best-First Sort
Insertion Sort
Quicker Sorting
Binary Trees
Quicksort
Searching
Unstructured Search
Binary Search
Indexed Search
Summary
Mutation
Assignment
Impact of Mutation
Names, Places, Frames, and Environments
Evaluation Rules with State
Mutable Pairs and Lists
Imperative Programming
List Mutators
Imperative Control Structures
Summary
Objects
Packaging Procedures and State
Encapsulation
Messages
Object Terminology
Inheritance
Implementing Subclasses
Overriding Methods
Object-Oriented Programming
Summary
Interpreters
Python
Python Programs
Data Types
Applications and Invocations
Control Statements
Parser
Evaluator
Primitives
If Expressions
Definitions and Names
Procedures
Application
Finishing the Interpreter
Lazy Evaluation
Lazy Interpreter
Lazy Programming
Summary
Computability
Mechanizing Reasoning
Gödel's Incompleteness Theorem
The Halting Problem
Universality
Proving Non-Computability
Summary
Indexes
Index
People