Surveying the field of computing
Surveying the field of computing is a survey of
techniques and results from computer science.
The book touches a number of areas, presenting a mix of
important and interesting results.
It covers elementary C++ programming, Internet architecture, and
Conceived for a CS course at a prestigious high school science
summer program (the Pennsylvania Governor's School for the
Sciences), the course is suitable as a one-semester introductory course
at the college or advanced high school level.
The third and most recent edition (as of June 1999) is
available on-line in PostScript
(655K, 142 pages) or gzipped Acrobat
If you find the textbook useful,
please e-mail me!
This will encourage me to continue posting editions on-line,
and even to edit what I post for a more general audience.
- First unit: Foundations
- Chapter 1: Overview, 3 pages.
- What is computer science? Outline. What to expect.
- Chapter 2: Problems and algorithms, 3 pages.
- Problems. Solutions. Undecidability.
- Chapter 3: High-level procedure, 4 pages.
- Pseudocode. Flowcharts.
- Second Unit: Programming
- Chapter 4: Programming overview, 4 pages.
- The programming process. A simple program. Typs for writing programs.
- Chapter 5: Variables, 5 pages.
- Basic data types. Declarations. Assignments. Expressions. Input and output.
- Chapter 6: Control statements, 9 pages.
- Conditional statements. Iteration statements. Extended example.
- Chapter 7: Functions, 3 pages.
- Function calls. Function definitions. Extended example. Parameters and variables.
- Chapter 8: Complex data types, 5 pages.
- Arrays. Strings. Structures.
- Chapter 9: Objects, 7 pages.
- Object-oriented design. Defining objects. Additional object concepts.
- Third unit: Recursion
- Chapter 10: Recursion, 8 pages
- Definition. Exponentiation. Tower of Hanoi.
- Chapter 11: Playing games, 6 pages
- Game tree search. Heuristics. Alpha-beta search
- Fourth unit: Internet
- Chapter 12: Networking fundamentals, 4 pages
- Representing data. Division of labor.
- Chapter 13: Transporting packets, 3 pages
- Machine names. Finding a route.
- Chapter 14: Putting packets together, 5 pages
- Connections. Reliable delivery.
- Chapter 15: Using messages, 2 pages
- HTTP. SMTP.
- Chapter 16: Cryptography, 6 pages
- Protocols. Private-key cryptography. Communicating an average.
- Fifth unit: Algorithms
- Chapter 17: Analyzing algorithm speed, 5 pages.
- Comparing algorithms. Finding big-O bounds.
- Chapter 18: Divide and conquer, 7 pages.
- Sorting. Multiplication.
- Chapter 19: Dynamic programming, 5 pages.
- Fibonacci numbers. Making change. All-pairs shortest paths.
- Sixth Unit: Appendices
- Appendix A: C++ quick-reference, 3 pages
- Appendix B: Symbols, 1 pages
- Appendix C: Mathematical concepts, 4 pages
- Logarithms. Induction. Geometric series. Recurrences. Graphs. Mathematical notation.
- Appendix D: Exercise solutions, 7 pages
- Index, 6 pages
All material copyright ©1999, Carl Burch. No part of the
publication may be transmitted to others,
in any form or by any means, mechanical, photocopying,
recording, or otherwise, without the prior written permission of the