Great ideas in computer science with Java

This book presents the "great ideas" of computer science, condensing a large amount of complex material into a manageable, accessible form; it does so using the Java programming language. The book is based on the problem-oriented approach that has been so successful in traditional quantitative sciences. For example, the reader learns about database systems by coding one in Java, about system architecture by reading and writing programs in assembly language, about compilation by hand-compiling Java statements into assembly language, and about noncomputability by studying a proof of noncomputability and learning to classify problems as either computable or noncomputable. The book covers an unusually broad range of material at a surprisingly deep level. It also includes chapters on networking and security. Even the reader who pursues computer science no further will acquire an understanding of the conceptual structure of computing and information technology that every well-informed citizen should have. Contents 8 Preface 13 Studying Academic Computer Science: An Introduction 18 1 The World Wide Web 23 World History and Where We Are 23 Let's Create Some Web Pages 24 More HTML 32 We Love HTML, But . . . 35 Summary 36 2 Watch Out: Here Comes Java 39 Let's Put Some Action into Those Web Pages 39 The Big Deal: Computer Programming 41 Object-Oriented Programming 41 The Java Programming Language 44 Decision Trees 44 Getting Started in Programming 49 Program Form and Statement Details 51 Program Execution 53 Interactive Programs and Buttons 57 Reading and Storing Data 62 Programming Decision Trees 73 *The Arrow Notation and Its Uses 86 *A Set of Rules for Java 100 Summary 102 3 Numerical Computation and a Study of Functions 105 Let's Calculate Some Numbers 105 Simple Calculations 106 Functions 117 Looping and a Study of Functions 119 Searching for the Best Value 126 Storing Information in Arrays 131 Finding Sums, Minima, and Maxima 139 Putting Things in a Row, and a Special Characteristic of Functions 145 *Putting the Functions in a Row 147 Summary 149 4 Top-Down Programming, Subroutines, and a Database Application 153 Let's Solve a Mystery 153 Top-Down Programming and the Database Program 154 Subroutines 157 Subroutines with Internal Variables 169 Subroutines with Array Parameters 172 Subroutine Communication Examples 178 Storing and Printing Facts for the Database 182 Representing Questions and Finding Their Answers 188 Assembling the Database Program and Adding Comments 193 *Recursion 202 Summary 208 5 Graphics, Classes, and Objects 213 Calling All Artists 213 Graphics Primitives 213 Let's Draw Some Pictures 217 Let's Create a Class Called House 221 Adding Features to the House Class 225 Creating a Village 229 Subclasses and the Java Class Hierarchy 231 Summary 235 6 Simulation 237 Predicting the Future 237 How Do You Win an Auto Race? A Simulation 238 *Avoiding the Plague: A Simulation 243 *Have You Ever Observed Evolution in Action? A Simulation 246 *What Will It Look Like? A Simulation 250 Summary 255 7 Software Engineering 257 The Real World 257 Lessons Learned from Large-Scale Programming Projects 258 Software Engineering Methodologies 260 The Program Life Cycle 264 Summary 267 8 Machine Architecture 269 When You Buy a Computer 269 A Sample Architecture: The P88 Machine 270 Programming the P88 Machine 274 Summary 280 9 Language Translation 283 Enabling the Computer to Understand Java 283 Syntactic Production Rules 284 Attaching Semantics to the Rules 290 The Semantics of Java 293 *The Translation of Looping Programs 302 Programming Languages 311 Summary 315 10 Virtual Environments for Computing 319 Use Your Imagination 319 Using an Operating System 322 Hardware Pragmatics 324 The Operating System 326 Files 331 *Contention for Memory and Paging 335 Summary 337 11 Security, Privacy, and Wishful Thinking 341 What's Really Going on Here? 341 Good Passwords and Cracking 343 Encryption 345 Modern Encryption 351 Public Key Encryption 352 Attacks 357 Summary 363 12 Computer Communications 367 Exploration 367 Layers and Local Area Networks ( LANs) 368 Wide Area Networks 372 The Internet Protocol ( IP) Layer and Above 374 *More on Addressing 376 Networked Servers 378 More Network-Based Applications 379 The Changing Internet 381 Summary 382 13 Program Execution Time 385 On the Limitations of Computer Science 385 Program Execution Time 386 Tractable Computations 387 Intractable Computations 394 Some Practical Problems with Very Expensive Solutions 399 Diagnosing Tractable and Intractable Problems 404 *Approximate Solutions to Intractable Problems 406 Summary 407 14 Parallel Computation 411 Using Many Processors Together 411 Parallel Computation 412 Communicating Processes 417 Parallel Computation on a Saturated Machine 422 Variations on Architecture 425 *Connectionist Architectures 427 *Learning the Connectionist Weights 434 Summary 441 15 Noncomputability 445 Speed Is Not Enough 445 On the Existence of Noncomputable Functions 445 Programs That Read Programs 450 Solving the Halting Problem 453 Examples of Noncomputable Problems 458 *Proving Noncomputability 460 Summary 464 16 Artificial Intelligence 467 The Dream 467 Representing Knowledge 470 Understanding 472 Learning 479 Frames 484 An Application: Natural Language Processing 486 Reasoning 493 Game Playing 503 *Game Playing: Historical Remarks 508 Expert Systems 511 Perspective 518 Summary 523 Appendix: The IntField and DoubleField Classes 525 Readings 533 Index 537 A broad yet deep presentation of the most important concepts in computer science, using the Java programming language for exercises.This book presents the'great ideas'of computer science, condensing a large amount of complex material into a manageable, accessible form; it does so using the Java programming language. The book is based on the problem-oriented approach that has been so successful in traditional quantitative sciences. For example, the reader learns about database systems by coding one in Java, about system architecture by reading and writing programs in assembly language, about compilation by hand-compiling Java statements into assembly language, and about noncomputability by studying a proof of noncomputability and learning to classify problems as either computable or noncomputable. The book covers an unusually broad range of material at a surprisingly deep level. It also includes chapters on networking and security. Even the reader who pursues computer science no further will acquire an understanding of the conceptual structure of computing and information technology that every well-informed citizen should have.