Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
About This E-Book
Title Page
Copyright Page
Dedication Page
Contents
Programs
Circuits
Preface
Coverage
Use in the Curriculum
Prerequisites
Goals
Online lectures
Booksite
Acknowledgments
Chapter One. Elements of Programming
1.1 Your First Program
Programming in Java
Input and output
Q&A
Exercises
1.2 Built-in Types of Data
Terminology
Characters and strings
Integers
Floating-point numbers
Booleans
Comparisons
Library methods and APIs
Type conversion
Summary
Q&A (Strings)
Q&A (Integers)
Q&A (Floating-Point Numbers)
Q&A (Variables and Expressions)
Exercises
Creative Exercises
1.3 Conditionals and Loops
If statements
While loops
For loops
Nesting
Applications
Other conditional and loop constructs
Infinite loops
Summary
Q&A
Exercises
Creative Exercises
1.4 Arrays
Arrays in Java
Coupon collector
Sieve of Eratosthenes
Two-dimensional arrays
Example: self-avoiding random walks
Summary
Q&A
Exercises
Creative Exercises
1.5 Input and Output
Bird’s-eye view
Standard output
Standard input
Redirection and piping
Standard drawing
Standard audio
Summary
Q&A
Exercises
Creative Exercises
1.6 Case Study: Random Web Surfer
Input format
Transition matrix
Simulation
Mixing a Markov chain
Lessons
Exercises
Creative Exercises
Chapter Two. Functions and Modules
2.1 Defining Functions
Static methods
Implementing mathematical functions
Using static methods to organize code
Passing arguments and returning values
Example: superposition of sound waves
Q&A
Exercises
Creative Exercises
2.2 Libraries and Clients
Using static methods in other programs
Libraries
Random numbers
Input and output for arrays
Iterated function systems
Statistics
Modular programming
Q&A
Exercises
Creative Exercises
2.3 Recursion
Your first recursive program
Mathematical induction
Euclid’s algorithm
Towers of Hanoi
Function-call trees
Exponential time
Gray codes
Recursive graphics
Brownian bridge
Pitfalls of recursion
Dynamic programming
Perspective
Q&A
Exercises
Creative Exercises
2.4 Case Study: Percolation
Percolation
Basic scaffolding
Vertical percolation
Testing
Estimating probabilities
Recursive solution for percolation
Adaptive plot
Lessons
Q&A
Exercises
Creative Exercises
Chapter Three. Object-Oriented Programming
3.1 Using Data Types
Basic definitions
String-processing application: genomics
Color
Digital image processing
Input and output revisited
Properties of reference types
Q&A
Exercises
Creative Exercises
3.2 Creating Data Types
Basic elements of a data type
Stopwatch
Histogram
Turtle graphics
Complex numbers
Mandelbrot set
Commercial data processing
Q&A
Exercises
Creative Exercises
3.3 Designing Data Types
Designing APIs
Encapsulation
Immutability
Example: spatial vectors
Interface inheritance (subtyping)
Implementation inheritance (subclassing)
Application: data mining
Design by contract
Q&A
Exercises
Data-Type Design Exercises
Creative Exercises
3.4 Case Study: N-Body Simulation
N-body simulation
Q&A
Exercises
Creative Exercises
Chapter Four. Algorithms and Data Structures
4.1 Performance
Scientific method
Observations
Hypotheses
Order-of-growth classifications
Predictions
Caveats
Performance guarantees
Memory
Perspective
Q&A
Exercises
Creative Exercises
4.2 Sorting and Searching
Binary search
Insertion sort
Mergesort
Application: frequency counts
Lessons
Q&A
Exercises
Creative Exercises
4.3 Stacks and Queues
Pushdown stacks
Array implementation
Linked lists
Resizing arrays
Parameterized data types
FIFO queues
Queue applications
Resource allocation
Q&A
Exercises
Linked-List Exercises
Creative Exercises
4.4 Symbol Tables
API
Symbol-table clients
Elementary symbol-table implementations
Hash tables
Binary search trees
Performance characteristics of BSTs
Traversing a BST
Ordered symbol table operations
Set data type
Perspective
Q&A
Exercises
Binary Tree Exercises
Creative Exercises
4.5 Case Study: Small-World Phenomenon
Graphs
Graph data type
Graph client example
Shortest paths in graphs
Small-world graphs
Lessons
Q&A
Exercises
Creative Exercises
Chapter Five. Theory of Computing
5.1 Formal Languages
Basic definitions
Regular languages
Generalized REs
Applications
Abstract machines
Deterministic finite-state automata
Java implementation of DFAs
Nondeterminism
Kleene’s theorem
Applications of Kleene’s theorem
Summary
Q&A
Exercises
Creative Exercises
5.2 Turing Machines
Turing machine model
Universal virtual Turing machine
Q&A
Exercises
Creative Exercises
5.3 Universality
Algorithms
Programs that process programs
Church–Turing Thesis
Variations on the TM model
Universal models
Q&A
Creative Exercises
5.4 Computability
Context: Hilbert’s program
Warmup: liar’s paradox
The halting problem
Reduction
More examples of unsolvable problems
Implications
Q&A
Exercises
Creative Exercises
5.5 Intractability
Overview
Examples
Satisfiability
Search problems
The main question
Polynomial-time reductions
NP-completeness
Proving problems to be NP-complete
Coping with NP-completeness
Q&A
Exercises
Creative Exercises
Chapter Six. A Computing Machine
6.1 Representing Information
Binary and Hexadecimal
Parsing and string representations
Integer arithmetic
Negative numbers
Real numbers
Java code for manipulating bits
Characters
Summary
Q&A
Exercises
Creative Exercises
6.2 TOY Machine
Brief historical note
TOY components
Fetch–increment–execute cycle
Instructions
Your first TOY program
Operating the machine
Conditionals and loops
Stored-program computing
Von Neumann machines
Q&A
Exercises
6.3 Machine-Language Programming
Functions
Standard output
Standard input
Arrays
Linked structures
Why learn machine-language programming?
Q&A
Exercises
Creative Exercises
6.4 TOY Virtual Machine
Booting and dumping
A note of caution
Programs that process programs
TOY in Java
The TOY family of imaginary computers
Q&A
Exercises
Creative Exercises
Chapter Seven. Building a Computing Device
7.1 Boolean Logic
Boolean functions
An application
Boolean functions of three or more variables
Exercises
Creative Exercises
7.2 Basic Circuit Model
Wires
Controlled switches
Circuits
Logical design and the real world
Q&A
Exercises
7.3 Combinational Circuits
Gates
Building a circuit from gates
Decoders, demuxes, and muxes
Sum-of-products circuits
Adder
Arithmetic logic unit (ALU)
Modules and buses
Layers of abstraction
Q&A
Exercises
Creative Exercises
7.4 Sequential Circuits
Elementary feedback circuits
Flip-flops
Registers
Memory
Clock
Summary
Q&A
Exercises
Creative Exercises
7.5 Digital Devices
TOY-8
Warmup
TOY-8 CPU organization and connections
Control
Example: A TOY-8 program
Perspective
Q&A
Exercises
Creative Exercises
Context
Java libraries
Programming environments
Scientific computing
Apps and cloud computing
Computer systems
Theory of computing
Machine learning
Glossary
Index
APIs
Code Snippets
← Prev
Back
Next →
← Prev
Back
Next →