An Invitation to Computer Science: Java Version

Chapter 1 An Introduction to Computer Science p. 1 1.1 Introduction p. 1 1.2 The Definition of Computer Science p. 4 1.3 Algorithms p. 11 1.3.1 The Formal Definition of an Algorithm p. 11 1.3.2 The Importance of Algorithmic Problem Solving p. 17 1.4 Organization of the Text p. 18 Level 1 The Algorithmic Foundations of Computer Science p. 26 Chapter 2 Algorithm Discovery and Design p. 29 2.1 Introduction p. 30 2.2 Representing Algorithms p. 30 2.2.1 Pseudocode p. 30 2.2.2 Sequential Operations p. 33 2.2.3 Conditional and Iterative Operations p. 36 2.3 Examples of Algorithmic Problem Solving p. 43 2.3.1 Example 1: Looking, Looking, Looking p. 43 2.3.2 Example 2: Big, Bigger, Biggest p. 47 2.3.3 Example 3: Meeting Your Match p. 54 2.4 Conclusion p. 60 Chapter 3 The Efficiency of Algorithms p. 65 3.1 Introduction p. 66 3.2 Attributes of Algorithms p. 66 3.3 A Choice of Algorithms p. 71 3.3.1 The Shuffle-Left Algorithm p. 71 3.3.2 The Copy-Over Algorithm p. 74 3.3.3 The Converging-Pointers Algorithm p. 75 3.3.4 Comparisons p. 76 3.4 Measuring Efficiency p. 77 3.4.1 Sequential Search p. 77 3.4.2 Order of Magnitude p. 80 3.5 Analysis of Algorithms p. 87 3.5.1 Data Cleanup p. 87 3.5.2 Selection Sort p. 89 3.5.3 Binary Search p. 95 3.5.4 Pattern Matching p. 101 3.5.5 Summary p. 102 3.6 When Things Get Out of Hand p. 103 3.7 Summary of Level 1 p. 114 Level 2 The Hardware World p. 116 Chapter 4 The Building Blocks: Binary Numbers, Boolean Logic, and Gates p. 119 4.1 Introduction p. 120 4.2 The Binary Numbering System p. 120 4.2.1 Binary Representation of Information p. 121 4.2.2 The Reliability of Binary Representation p. 129 4.2.3 Binary Storage Devices p. 131 4.3 Boolean Logic and Gates p. 137 4.3.1 Boolean Logic p. 137 4.3.2 Gates p. 141 4.4 Building Computer Circuits p. 144 4.4.1 Introduction p. 144 4.4.2 A Circuit Construction Algorithm p. 147 4.4.3 Examples of Circuit Design and Construction p. 152 4.4.4 Summary p. 160 4.5 Control Circuits p. 160 4.6 Conclusion p. 165 Chapter 5 Computer Systems Organization p. 169 5.1 Introduction p. 170 5.2 The von Neumann Architecture p. 173 5.2.1 Memory and Cache p. 174 5.2.2 Input/Output and Mass Storage p. 184 5.2.3 The Arithmetic/Logic Unit p. 190 5.2.4 The Control Unit p. 194 5.2.5 Putting All the Pieces Together p. 202 5.3 Historical Overview of Computer Systems Development p. 208 5.3.1 The Early Period: Up to 1940 p. 208 5.3.2 The Birth of Computers: 1940-1950 p. 213 5.3.3 The Modern Era: 1950 to the Present p. 216 5.3.4 The Future: Non-Von Neumann Machines p. 221 5.4 Summary of Level 2 p. 231 Level 3 The Virtual Machine p. 232 Chapter 6 An Introduction to System Software and Virtual Machines p. 235 6.1 Introduction p. 236 6.2 System Software p. 237 6.2.1 The Virtual Machine p. 237 6.2.2 Types of System Software p. 239 6.3 Assemblers and Assembly Language p. 240 6.3.1 Assembly Language p. 240 6.3.2 Examples of Assembly Language Code p. 248 6.3.3 Translation and Loading p. 252 6.4 Operating Systems p. 261 6.4.1 Functions of an Operating System p. 261 6.4.2 Historical Overview of Operating Systems Development p. 272 6.4.3 The Future p. 282 6.5 Summary of Level 3 p. 288 Level 4 The Software World p. 290 Chapter 7 Introduction to High-Level Language Programming p. 293 7.1 Where Do We Stand? p. 294 7.2 High-Level Languages p. 295 7.3 Introduction to Java p. 298 7.3.1 A Simple Java Program p. 298 7.3.2 Running a Java Program p. 301 7.4 Virtual Data Storage p. 301 7.5 Statement Types p. 306 7.5.1 Input Statements p. 306 7.5.2 Output Statements p. 309 7.5.3 The Assignment Statement p. 311 7.5.4 Control Statements p. 314 7.5.5 Another Example p. 327 7.6 Meeting Expectations p. 331 7.7 Managing Complexity p. 335 7.7.1 Divide and Conquer p. 335 7.7.2 Using Methods p. 336 7.7.3 Writing Methods p. 339 7.8 Object-Oriented Program p. 347 7.8.1 What Is It? p. 347 7.8.2 Java and OOP p. 349 7.8.3 One More Example p. 354 7.8.4 What Have We Gained? p. 359 7.9 Graphical Programming p. 361 7.9.1 The Importance of Visualization p. 361 7.9.2 Graphics Hardware p. 363 7.9.3 Graphics Software p. 365 7.10 The Big Picture: Software Engineering p. 375 7.10.1 Scaling Up p. 377 7.10.2 The Software Life Cycle p. 377 7.11 Conclusion p. 383 Chapter 8 The Tower of Babel p. 391 8.1 Why Babel? p. 392 8.2 Procedural Languages p. 393 8.2.1 Fortran p. 394 8.2.2 Cobol p. 396 8.2.3 Pascal p. 399 8.2.4 C/C++ p. 400 8.2.5 Ada p. 404 8.2.6 A Final World p. 405 8.3 Special-Purpose Languages p. 406 8.3.1 SQL p. 406 8.3.2 Perl p. 407 8.3.3 HTML p. 408 8.4 Alternative Programming Paradigms p. 411 8.4.1 Functional Programming p. 412 8.4.2 Logic Programming p. 417 8.4.3 Parallel Programming p. 423 8.5 Conclusion p. 426 Chapter 9 Compilers and Language Translation p. 433 9.1 Introduction p. 434 9.2 The Compilation Process p. 437 9.2.1 Phase I: Lexical Analysis p. 438 9.2.2 Phase II: Parsing p. 442 9.2.3 Phase III: Semantics and Code Generation p. 460 9.2.4 Phase IV: Code Optimization p. 470 9.3 Conclusion p. 475 Chapter 10 Models of Computation p. 481 10.1 Introduction p. 482 10.2 What Is a Model? p. 482 10.3 A Model of a Computing Agent p. 485 10.3.1 Properties of a Computing Agent p. 485 10.3.2 The Turing Machine p. 486 10.4 A Model of an Algorithm p. 495 10.5 Turing Machine Examples p. 498 10.5.1 A Bit Inverter p. 498 10.5.2 A Parity Bit Machine p. 500 10.5.3 Machines for Unary Incrementing p. 503 10.5.4 A Unary Addition Machine p. 506 10.6 The Church-Turing Thesis p. 508 10.7 Unsolvable Problems p. 512 10.8 Conclusion p. 517 10.9 Summary of Level 4 p. 523 Level 5 Applications p. 524 Chapter 11 Using and Managing Data: A Case Study in Three Scenes p. 527 11.1 Introduction p. 528 11.2 Spreadsheets p. 528 11.2.1 Basic Spreadsheet Operation p. 528 11.2.2 Bells and Whistles p. 531 11.2.3 Spreadsheets as Modeling Tools p. 533 11.2.4 Computer Science Issues p. 536 11.3 File Management and Databases p. 539 11.3.1 Basic File Management p. 539 11.3.2 Data Organization p. 541 11.3.3 Database Management Systems p. 542 11.3.4 Odds and Ends p. 547 11.3.5 Computer Science Issues p. 547 11.4 Numeric and Symbolic Computation p. 549 11.4.1 The Importance of Numeric Applications p. 549 11.4.2 Symbolic Computing p. 551 11.4.3 The Case Study p. 559 11.4.4 Computer Science Issues p. 563 11.5 Conclusion p. 566 Chapter 12 Computer Networks p. 569 12.1 Introduction p.