Surveying the field of computing

By Carl Burch

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 algorithm design.

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 (759K) formats.

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 author.