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. Cover......Page 1 Contents......Page 8 Preface......Page 13 Studying Academic Computer Science: An Introduction......Page 18 World History and Where We Are......Page 23 Let's Create Some Web Pages......Page 24 More HTML......Page 32 We Love HTML, But . . .......Page 35 Summary......Page 36 Let's Put Some Action into Those Web Pages......Page 39 Object-Oriented Programming......Page 41 Decision Trees......Page 44 Getting Started in Programming......Page 49 Program Form and Statement Details......Page 51 Program Execution......Page 53 Interactive Programs and Buttons......Page 57 Reading and Storing Data......Page 62 Programming Decision Trees......Page 73 *The Arrow Notation and Its Uses......Page 86 *A Set of Rules for Java......Page 100 Summary......Page 102 Let's Calculate Some Numbers......Page 105 Simple Calculations......Page 106 Functions......Page 117 Looping and a Study of Functions......Page 119 Searching for the Best Value......Page 126 Storing Information in Arrays......Page 131 Finding Sums, Minima, and Maxima......Page 139 Putting Things in a Row, and a Special Characteristic of Functions......Page 145 *Putting the Functions in a Row......Page 147 Summary......Page 149 Let's Solve a Mystery......Page 153 Top-Down Programming and the Database Program......Page 154 Subroutines......Page 157 Subroutines with Internal Variables......Page 169 Subroutines with Array Parameters......Page 172 Subroutine Communication Examples......Page 178 Storing and Printing Facts for the Database......Page 182 Representing Questions and Finding Their Answers......Page 188 Assembling the Database Program and Adding Comments......Page 193 *Recursion......Page 202 Summary......Page 208 Graphics Primitives......Page 213 Let's Draw Some Pictures......Page 217 Let's Create a Class Called House......Page 221 Adding Features to the House Class......Page 225 Creating a Village......Page 229 Subclasses and the Java Class Hierarchy......Page 231 Summary......Page 235 Predicting the Future......Page 237 How Do You Win an Auto Race? A Simulation......Page 238 *Avoiding the Plague: A Simulation......Page 243 *Have You Ever Observed Evolution in Action? A Simulation......Page 246 *What Will It Look Like? A Simulation......Page 250 Summary......Page 255 The Real World......Page 257 Lessons Learned from Large-Scale Programming Projects......Page 258 Software Engineering Methodologies......Page 260 The Program Life Cycle......Page 264 Summary......Page 267 When You Buy a Computer......Page 269 A Sample Architecture: The P88 Machine......Page 270 Programming the P88 Machine......Page 274 Summary......Page 280 Enabling the Computer to Understand Java......Page 283 Syntactic Production Rules......Page 284 Attaching Semantics to the Rules......Page 290 The Semantics of Java......Page 293 *The Translation of Looping Programs......Page 302 Programming Languages......Page 311 Summary......Page 315 Use Your Imagination......Page 319 Using an Operating System......Page 322 Hardware Pragmatics......Page 324 The Operating System......Page 326 Files......Page 331 *Contention for Memory and Paging......Page 335 Summary......Page 337 What's Really Going on Here?......Page 341 Good Passwords and Cracking......Page 343 Encryption......Page 345 Modern Encryption......Page 351 Public Key Encryption......Page 352 Attacks......Page 357 Summary......Page 363 Exploration......Page 367 Layers and Local Area Networks ( LANs)......Page 368 Wide Area Networks......Page 372 The Internet Protocol ( IP) Layer and Above......Page 374 *More on Addressing......Page 376 Networked Servers......Page 378 More Network-Based Applications......Page 379 The Changing Internet......Page 381 Summary......Page 382 On the Limitations of Computer Science......Page 385 Program Execution Time......Page 386 Tractable Computations......Page 387 Intractable Computations......Page 394 Some Practical Problems with Very Expensive Solutions......Page 399 Diagnosing Tractable and Intractable Problems......Page 404 *Approximate Solutions to Intractable Problems......Page 406 Summary......Page 407 Using Many Processors Together......Page 411 Parallel Computation......Page 412 Communicating Processes......Page 417 Parallel Computation on a Saturated Machine......Page 422 Variations on Architecture......Page 425 *Connectionist Architectures......Page 427 *Learning the Connectionist Weights......Page 434 Summary......Page 441 On the Existence of Noncomputable Functions......Page 445 Programs That Read Programs......Page 450 Solving the Halting Problem......Page 453 Examples of Noncomputable Problems......Page 458 *Proving Noncomputability......Page 460 Summary......Page 464 The Dream......Page 467 Representing Knowledge......Page 470 Understanding......Page 472 Learning......Page 479 Frames......Page 484 An Application: Natural Language Processing......Page 486 Reasoning......Page 493 Game Playing......Page 503 *Game Playing: Historical Remarks......Page 508 Expert Systems......Page 511 Perspective......Page 518 Summary......Page 523 Appendix: The IntField and DoubleField Classes......Page 525 Readings......Page 533 Index......Page 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.