Computer Science : An Interdisciplinary Approach

Named a Notable Book in the 21st Annual Best of Computing list by the ACM! Robert Sedgewick and Kevin Wayne's Computer Science: An Interdisciplinary Approach is the ideal modern introduction to computer science with Java programming for both students and professionals. Taking a broad, applications-based approach, Sedgewick and Wayne teach through important examples from science, mathematics, engineering, finance, and commercial computing. The book demystifies computation, explains its intellectual underpinnings, and covers the essential elements of programming and computational problem solving in today's environments. The authors begin by introducing basic programming elements such as variables, conditionals, loops, arrays, and I/O. Next, they turn to functions, introducing key modular programming concepts, including components and reuse. They present a modern introduction to object-oriented programming, covering current programming paradigms and approaches to data abstraction. Building on this foundation, Sedgewick and Wayne widen their focus to the broader discipline of computer science. They introduce classical sorting and searching algorithms, fundamental data structures and their application, and scientific techniques for assessing an implementation's performance. Using abstract models, readers learn to answer basic questions about computation, gaining insight for practical application. Finally, the authors show how machine architecture links the theory of computing to real computers, and to the field's history and evolution. For each concept, the authors present all the information readers need to build confidence, together with examples that solve intriguing problems. Each chapter contains question-and-answer sections, self-study drills, and challenging problems that demand creative solutions. Companion web site ((http://introcs.cs.princeton.edu/java) introcs.cs.princeton.edu/java ) contains Extensive supplementary information, including suggested approaches to programming assignments, checklists, and FAQs Graphics and sound libraries Links to program code and test data Solutions to selected exercises Chapter summaries Detailed instructions for installing a Java programming environment Detailed problem sets and projects Companion 20-part series of video lectures is available at(http://informit.com/title/9780134493831) informit.com/title/9780134493831 Cover......Page 1 Title......Page 4 Copyright......Page 5 Contents......Page 7 Programs......Page 9 Circuits......Page 12 Preface......Page 14 Coverage......Page 15 Use in the Curriculum......Page 16 Prerequisites......Page 17 Goals......Page 18 Booksite......Page 19 Acknowledgments......Page 20 1—Elements of Programming......Page 22 Programming in Java......Page 23 Input and output......Page 28 Q&A......Page 30 Exercises......Page 33 1.2 Built-in Types of Data......Page 35 Terminology......Page 36 Characters and strings......Page 40 Integers......Page 43 Floating-point numbers......Page 45 Booleans......Page 47 Comparisons......Page 48 Library methods and APIs......Page 50 Type conversion......Page 53 Summary......Page 56 Q&A (Strings)......Page 58 Q&A (Integers)......Page 59 Q&A (Floating-Point Numbers)......Page 61 Q&A (Variables and Expressions)......Page 63 Exercises......Page 65 Creative Exercises......Page 68 If statements......Page 71 While loops......Page 74 For loops......Page 80 Nesting......Page 83 Applications......Page 85 Other conditional and loop constructs......Page 95 Infinite loops......Page 97 Summary......Page 98 Q&A......Page 99 Exercises......Page 102 Creative Exercises......Page 107 1.4 Arrays......Page 111 Arrays in Java......Page 112 Coupon collector......Page 122 Sieve of Eratosthenes......Page 124 Two-dimensional arrays......Page 127 Example: self-avoiding random walks......Page 133 Summary......Page 136 Q&A......Page 137 Exercises......Page 139 Creative Exercises......Page 142 1.5 Input and Output......Page 147 Bird’s-eye view......Page 148 Standard output......Page 150 Standard input......Page 153 Redirection and piping......Page 160 Standard drawing......Page 165 Standard audio......Page 176 Summary......Page 180 Q&A......Page 181 Exercises......Page 183 Creative Exercises......Page 188 1.6 Case Study: Random Web Surfer......Page 191 Input format......Page 192 Transition matrix......Page 193 Simulation......Page 195 Mixing a Markov chain......Page 200 Lessons......Page 205 Exercises......Page 207 Creative Exercises......Page 209 2—Functions and Modules......Page 212 2.1 Defining Functions......Page 213 Static methods......Page 214 Implementing mathematical functions......Page 223 Using static methods to organize code......Page 226 Passing arguments and returning values......Page 228 Example: superposition of sound waves......Page 232 Q&A......Page 237 Exercises......Page 239 Creative Exercises......Page 243 2.2 Libraries and Clients......Page 247 Using static methods in other programs......Page 248 Libraries......Page 251 Random numbers......Page 253 Input and output for arrays......Page 258 Iterated function systems......Page 260 Statistics......Page 265 Modular programming......Page 272 Q&A......Page 276 Exercises......Page 277 Creative Exercises......Page 280 2.3 Recursion......Page 283 Your first recursive program......Page 285 Mathematical induction......Page 287 Euclid’s algorithm......Page 288 Towers of Hanoi......Page 289 Function-call trees......Page 290 Exponential time......Page 293 Gray codes......Page 294 Recursive graphics......Page 297 Brownian bridge......Page 299 Pitfalls of recursion......Page 302 Dynamic programming......Page 305 Perspective......Page 310 Q&A......Page 311 Exercises......Page 312 Creative Exercises......Page 315 2.4 Case Study: Percolation......Page 321 Percolation......Page 322 Basic scaffolding......Page 323 Testing......Page 326 Estimating probabilities......Page 329 Recursive solution for percolation......Page 333 Adaptive plot......Page 335 Lessons......Page 339 Q&A......Page 342 Exercises......Page 343 Creative Exercises......Page 345 3—Object-Oriented Programming......Page 350 3.1 Using Data Types......Page 351 Basic definitions......Page 352 String-processing application: genomics......Page 357 Color.......Page 362 Digital image processing......Page 367 Input and output revisited......Page 374 Properties of reference types......Page 383 Q&A......Page 390 Exercises......Page 394 Creative Exercises......Page 398 3.2 Creating Data Types......Page 403 Basic elements of a data type......Page 404 Stopwatch......Page 411 Histogram......Page 413 Turtle graphics......Page 415 Complex numbers......Page 423 Mandelbrot set......Page 427 Commercial data processing......Page 431 Q&A......Page 436 Exercises......Page 439 Creative Exercises......Page 444 3.3 Designing Data Types......Page 449 Designing APIs......Page 450 Encapsulation......Page 453 Immutability......Page 460 Example: spatial vectors......Page 463 Interface inheritance (subtyping)......Page 467 Implementation inheritance (subclassing)......Page 473 Application: data mining......Page 479 Design by contract......Page 486 Q&A......Page 489 Exercises......Page 492 Data-Type Design Exercises......Page 495 Creative Exercises......Page 497 3.4 Case Study: N-Body Simulation......Page 499 N-body simulation......Page 500 Q&A......Page 510 Exercises......Page 511 Creative Exercises......Page 512 4—Algorithms and Data Structures......Page 514 4.1 Performance......Page 515 Observations......Page 516 Hypotheses......Page 517 Order-of-growth classifications......Page 524 Predictions......Page 528 Caveats......Page 530 Performance guarantees......Page 533 Memory......Page 534 Perspective......Page 539 Q&A......Page 540 Exercises......Page 543 Creative Exercises......Page 550 4.2 Sorting and Searching......Page 553 Binary search......Page 554 Insertion sort......Page 564 Mergesort......Page 571 Application: frequency counts......Page 576 Lessons......Page 579 Q&A......Page 580 Exercises......Page 581 Creative Exercises......Page 584 4.3 Stacks and Queues......Page 587 Pushdown stacks......Page 588 Array implementation......Page 589 Linked lists......Page 592 Resizing arrays......Page 599 Parameterized data types......Page 603 Stack applications......Page 607 FIFO queues......Page 613 Queue applications......Page 618 Iterable collections......Page 622 Resource allocation......Page 627 Q&A......Page 630 Exercises......Page 633 Linked-List Exercises......Page 637 Creative Exercises......Page 639 4.4 Symbol Tables......Page 645 API......Page 646 Symbol-table clients......Page 649 Elementary symbol-table implementations......Page 656 Hash tables......Page 657 Binary search trees......Page 661 Performance characteristics of BSTs......Page 668 Traversing a BST......Page 670 Ordered symbol table operations......Page 672 Set data type......Page 673 Perspective......Page 675 Q&A......Page 676 Exercises......Page 677 Binary Tree Exercises......Page 682 Creative Exercises......Page 684 4.5 Case Study: Small-World Phenomenon......Page 691 Graphs......Page 692 Graph data type......Page 696 Graph client example......Page 700 Shortest paths in graphs......Page 704 Small-world graphs......Page 714 Lessons......Page 721 Q&A......Page 724 Exercises......Page 726 Creative Exercises......Page 730 5—Theory of Computing......Page 736 Basic definitions......Page 739 Regular languages......Page 744 Generalized REs......Page 751 Applications......Page 753 Abstract machines......Page 758 Deterministic finite-state automata......Page 759 Java implementation of DFAs.......Page 762 Nondeterminism......Page 765 Kleene’s theorem......Page 769 Applications of Kleene’s theorem......Page 774 Summary......Page 777 Q&A......Page 778 Exercises......Page 780 Creative Exercises......Page 783 Turing machine model......Page 787 Universal virtual Turing machine......Page 795 Q&A......Page 801 Exercises......Page 802 Creative Exercises......Page 805 Algorithms......Page 807 Programs that process programs......Page 809 Church–Turing Thesis......Page 811 Variations on the TM model......Page 812 Universal models......Page 815 Q&A......Page 819 Creative Exercises......Page 820 Context: Hilbert’s program......Page 827 Warmup: liar’s paradox......Page 828 The halting problem......Page 829 Reduction......Page 832 More examples of unsolvable problems......Page 834 Implications......Page 837 Q&A......Page 839 Exercises......Page 840 Creative Exercises......Page 841 5.5 Intractability......Page 843 Overview......Page 844 Examples......Page 847 Satisfiability......Page 851 Search problems......Page 854 The main question......Page 861 Polynomial-time reductions......Page 862 Proving problems to be NP-complete......Page 865 Coping with NP-completeness......Page 871 Q&A......Page 879 Exercises......Page 882 Creative Exercises......Page 889 6—A Computing Machine......Page 894 6.1 Representing Information......Page 895 Binary and Hexadecimal......Page 896 Parsing and string representations......Page 901 Integer arithmetic......Page 905 Negative numbers......Page 907 Real numbers......Page 909 Java code for manipulating bits......Page 912 Characters......Page 915 Summary......Page 917 Q&A......Page 918 Exercises......Page 922 Creative Exercises......Page 926 6.2 TOY Machine......Page 927 Brief historical note......Page 928 TOY components......Page 929 Fetch–increment–execute cycle......Page 931 Instructions......Page 932 Your first TOY program......Page 935 Operating the machine......Page 937 Conditionals and loops......Page 939 Stored-program computing......Page 943 Von Neumann machines......Page 945 Q&A......Page 947 Exercises......Page 948 6.3 Machine-Language Programming......Page 951 Functions......Page 952 Standard output......Page 955 Standard input......Page 957 Arrays......Page 959 Linked structures......Page 963 Why learn machine-language programming?......Page 966 Q&A......Page 968 Exercises......Page 969 Creative Exercises......Page 976 6.4 TOY Virtual Machine......Page 979 Booting and dumping......Page 980 A note of caution......Page 982 Programs that process programs......Page 985 TOY in Java......Page 987 The TOY family of imaginary computers......Page 993 Q&A......Page 999 Exercises......Page 1000 Creative Exercises......Page 1001 7—Building a Computing Device......Page 1006 7.1 Boolean Logic......Page 1007 Boolean functions......Page 1008 An application......Page 1013 Boolean functions of three or more variables......Page 1015 Exercises......Page 1019 Creative Exercises......Page 1021 7.2 Basic Circuit Model......Page 1023 Wires......Page 1024 Controlled switches......Page 1026 Circuits......Page 1027 Logical design and the real world......Page 1029 Q&A......Page 1031 Exercises......Page 1032 7.3 Combinational Circuits......Page 1033 Gates......Page 1034 Building a circuit from gates......Page 1040 Decoders, demuxes, and muxes......Page 1042 Sum-of-products circuits......Page 1045 Adder......Page 1049 Arithmetic logic unit (ALU)......Page 1052 Modules and buses......Page 1055 Layers of abstraction......Page 1058 Q&A......Page 1062 Exercises......Page 1063 Creative Exercises......Page 1066 Elementary feedback circuits......Page 1069 Flip-flops......Page 1070 Registers......Page 1072 Memory......Page 1075 Clock......Page 1079 Summary......Page 1083 Q&A......Page 1085 Exercises......Page 1086 Creative Exercises......Page 1088 TOY-8......Page 1091 Warmup......Page 1094 TOY-8 CPU organization and connections......Page 1097 Control......Page 1101 Example: A TOY-8 program......Page 1103 Perspective......Page 1105 Q&A......Page 1109 Exercises......Page 1110 Creative Exercises......Page 1111 Context......Page 1114 B......Page 1118 C......Page 1119 G......Page 1120 I......Page 1121 M......Page 1122 O......Page 1123 P......Page 1124 T......Page 1125 W......Page 1126 A......Page 1128 B......Page 1130 C......Page 1131 D......Page 1134 E......Page 1136 F......Page 1137 H......Page 1139 I......Page 1140 L......Page 1142 M......Page 1143 N......Page 1145 O......Page 1146 P......Page 1147 R......Page 1149 S......Page 1151 T......Page 1154 V......Page 1156 Z......Page 1157 Math......Page 1159 System.out/StdOut/Out......Page 1160 StdIn/In......Page 1161 StdDraw......Page 1162 Picture......Page 1163 StdStats......Page 1164 SET......Page 1165 Graph......Page 1166 Named a Notable Book in the 21st Annual Best of Computing list by the ACM!Robert Sedgewick and Kevin Wayne’s __**Computer Science: An Interdisciplinary Approach**__ is the ideal modern introduction to computer science with Java programming for both students and professionals. Taking a broad, applications-based approach, Sedgewick and Wayne teach through important examples from science, mathematics, engineering, finance, and commercial computing. The book demystifies computation, explains its intellectual underpinnings, and covers the essential elements of programming and computational problem solving in today’s environments. The authors begin by introducing basic programming elements such as variables, conditionals, loops, arrays, and I/O. Next, they turn to functions, introducing key modular programming concepts, including components and reuse. They present a modern introduction to object-oriented programming, covering current programming paradigms and approaches to data abstraction. Building on this foundation, Sedgewick and Wayne widen their focus to the broader discipline of computer science. They introduce classical sorting and searching algorithms, fundamental data structures and their application, and scientific techniques for assessing an implementation’s performance. Using abstract models, readers learn to answer basic questions about computation, gaining insight for practical application. Finally, the authors show how machine architecture links the theory of computing to real computers, and to the field’s history and evolution. For each concept, the authors present all the information readers need to build confidence, together with examples that solve intriguing problems. Each chapter contains question-and-answer sections, self-study drills, and challenging problems that demand creative solutions. **Companion web site** (introcs.cs.princeton.edu/java) contains * Extensive supplementary information, including suggested approaches to programming assignments, checklists, and FAQs * Graphics and sound libraries * Links to program code and test data * Solutions to selected exercises * Chapter summaries * Detailed instructions for installing a Java programming environment * Detailed problem sets and projects **Companion 20-part series of video lectures** is available at informit.com/title/9780134493831 Today, learning to program and understanding the basics of computation isn't just indispensable for every science and engineering student: it's crucial for everyone who wants to understand the world they live in. In Computer Science: An Interdisciplinary Approach, pioneering Princeton computer science professors Robert Sedgewick and Kevin Wayne introduce core Java programming techniques in a scientific context, while also demystifying computation and illuminating its intellectual underpinnings. Writing for students and professionals of all types and backgrounds, Sedgewick and Wayne draw on all they've learned in teaching hundreds of thousands of beginners worldwide, both in person and online. The companion text to their eagerly-anticipated Course: Computer Science MOOC, this book's intelligent, broad-based approach draws on applications from science, mathematics, engineering, and commercial computing. Throughout, they engage students by teaching how to solve interesting and significant problems - not toy problems. Coverage includes: Elements of programming: built-in data types, conditionals, loops, arrays, I/O, and more; Functions and modules: static methods, libraries, clients, and recursion; Object-oriented programming: understanding, creating, and designing data types; Algorithms and data structures: performance, sorting, searching, stacks, queues, and symbol tables; Computing machines: data representations, instruction set architecture, programming, simulations, and more; Building a computer: gates, circuits, components, and CPUs; Theory of computation: formal languages, abstract machines, computability, universality, and intractability. Each chapter contains questions and answers, exercises, creative exercises, and a compelling, classroom-tested case study - all reflecting Sedgewick and Wayne's years of experience teaching introductory computer science at Princeton. The book is complemented by extensive resources on a comprehensive website, including hundreds of Java programs and real-world data sets. -- Provided by publisher Today, learning to program and understanding the basics of computation isn't just indispensable for every science and engineering student: it's crucial for everyone who wants to understand the world they live in. InComputer Science: An Interdisciplinary Approach, pioneering Princeton computer science professors Robert Sedgewick and Kevin Wayne introduce core Java programming techniques in a scientific context, while also demystifying computation and illuminating its intellectual underpinnings. Writing for students and professionals of all types and backgrounds, Sedgewick and Wayne draw on all they've learned in teaching hundreds of thousands of beginners worldwide, both in person and online. The companion text to their eagerly-anticipated Coursera Computer Science MOOC, this book's intelligent, broad-based approach draws on applications from science, mathematics, engineering, and commercial computing. Throughout, they engage students by teaching how to solve interesting and significant problems - not toy problems. Coverage includes:Elements of programming: built-in data types, conditionals, loops, arrays, I/O, and moreFunctions and modules: static methods, libraries, clients, and recursionObject-oriented programming: understanding, creating, and designing data typesAlgorithms and data structures: performance, sorting, searching, stacks, queues, and symbol tablesComputing machines: data representations, instruction set architecture, programming, simulations, and moreBuilding a computer: gates, circuits, components, and CPUsTheory of computation: formal languages, abstract machines, computability, universality, and intractabilityEach chapter contains questions and answers, exercises, creative exercises, and a compelling, classroom-tested case study - all reflecting Sedgewick and Wayne's 20+ years of experience teaching introductory computer science at Princeton. The book is complemented by extensive resources on a comprehensive website, including hundreds of Java programs and real-world data sets. -- Provided by publisher The ideal modern introduction to computer science with Java programming for both students and professionals. Taking a broad, applications-based approach, Sedgewick and Wayne teach through important examples from science, mathematics, engineering, finance, and commercial computing. Today, learning to program and understanding the basics of computation isn't just indispensable for every science and engineering student: it's crucial for everyone who wants to understand the world they live in. In Computer Science: An Interdisciplinary Approach, pioneering Princeton computer science professors Robert Sedgewick and Kevin Wayne introduce core Java programming techniques in a scientific context, while also demystifying computation and illuminating its intellectual underpinnings