Computer Science: An Interdisciplinary Approach

1 ComputerScienceThis page intentionally left blank ComputerScienceAn Interdisciplinary ApproachRobert SedgewickKevin WaynePrinceton UniversityBoston Columbus Indianapolis New York San Francisco Amsterdam Cape TownDubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico CityS o Paulo Sydney Hong Kong Seoul Singapore Taipei TokyoMany of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trade-mark claim, the designations have been printed with initial capital letters or in all authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions.

2 No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions; custom cover designs; and content particular to your business, train-ing goals, marketing focus, or branding interests), please contact our corporate sales department at or (800) government sales inquiries, please contact questions about sales outside the United States, please contact us on the Web: of Congress Control Number: 2016936496 Copyright 2017 Pearson Education, rights reserved. Printed in the United States of America. This publication is protected by copy-right, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise.

3 For information regarding permissions, request forms, and the appropriate contacts within the Pearson Education Global Rights & Permissions Department, please visit : 978-0-13-407642-3 ISBN-10: 0-13-407642-7 Text printed in the United States on recycled paper at RR Donnelley in Crawfordsville, printing, June 2016_____ To Adam, Andrew, Brett, Robbie,Henry, Iona, Rose, Peter,and especially Linda_____ To Jackie, Alex, and Michael_____viContentsPreface .. xiii1 Elements of Programming .. Your First Program Built-in Types of Data Conditionals and Loops Input and Output Case Study: Random Web Surfer 1702 Functions and Modules .. Defining Functions Libraries and Recursion Case Study: Percolation 3003 Object-Oriented Programming .. Using Data Types Creating Data Designing Data Types Case Study: N-Body Simulation 4784 Algorithms and Data Structures.

4 Performance Sorting and Stacks and Queues Symbol Tables Case Study: Small-World Phenomenon 670vii5 Theory of Computing .. Formal Languages Turing Machines Universality Computability Intractability 8226 A Computing Machine .. Representing Information TOY Machine Machine-Language Programming TOY Virtual Machine 9587 Building a Computing Device .. Boolean Logic Basic Circuit Model Combinational Circuits Sequential Circuits Digital Devices 1070 Context.. 1093 Glossary .. 1097 Index .. 1107 APIs .. 1139viiiElements of ProgrammingYour First Hello, World .. Using a command-line argument 7 Built-in Types of String concatenation .. Integer multiplication and division Quadratic formula .. Leap year .. Casting to get a random integer.

5 34 Conditionals and Flipping a fair coin .. Your first while loop .. Computing powers of 2 .. Your first nested loops .. Harmonic numbers .. Newton s method .. Converting to binary .. Gambler s ruin simulation .. Factoring integers .. Sampling without replacement .. Coupon collector simulation .. Sieve of Eratosthenes .. Self-avoiding random walks .. 113 Input and Generating a random sequence Interactive user input .. Averaging a stream of numbers A simple filter .. Standard input-to-drawing filter Bouncing ball .. Digital signal processing ..158 Case Study: Random Web Computing the transition matrix Simulating a random surfer .. Mixing a Markov chain .. 182 Functions and ModulesDefining Harmonic numbers (revisited) Gaussian functions.

6 Coupon collector (revisited) .. Play that tune (revisited) .. 213 Libraries and Random number library .. Array I/O library .. Iterated function systems .. Data analysis library .. Plotting data values in an array Bernoulli trials .. Euclid s algorithm.. Towers of Hanoi .. Gray code .. Recursive graphics .. Brownian bridge .. Longest common subsequence 287 Case Study: Percolation scaffolding.. Vertical percolation detection .. Visualization client .. Percolation probability estimate Percolation detection .. Adaptive plot client .. 316 ProgramsixObject-Oriented ProgrammingUsing Data Identifying a potential gene .. Albers squares .. Luminance library .. Converting color to grayscale .. Image scaling .. Fade effect .. Concatenating files.

7 Screen scraping for stock quotes Splitting a file .. 360 Creating Data Charged particle .. Stopwatch .. Histogram .. Turtle graphics .. Spira mirabilis .. Complex number .. Mandelbrot set .. Stock account .. 413 Designing Data Complex number (alternate) .. Counter .. Spatial vectors .. Document sketch .. Similarity detection .. 463 Case Study: N-Body Gravitational body .. N-body simulation .. 485 Algorithms and Data 3-sum problem .. Validating a doubling hypothesis 499 Sorting and Binary search (20 questions) .. Bisection search .. Binary search (sorted array) .. Insertion sort .. Doubling test for insertion sort Mergesort .. Frequency counts .. 557 Stacks and Stack of strings (array).. Stack of strings (linked list) .. Stack of strings (resizing array) Generic stack.

8 Expression evaluation .. Generic FIFO queue (linked list) M/M/1 queue simulation .. Load balancing simulation .. 607 Symbol Dictionary lookup .. Indexing.. Hash table .. Binary search tree .. Dedup filter .. 653 Case Study: Small-World Graph data type .. Using a graph to invert an index Shortest-paths client .. Shortest-paths implementation Small-world test .. performer graph.. 698xTheory of ComputingFormal RE recognition .. Generalized RE pattern match Universal virtual DFA .. 743 Turing Virtual Turing machine tape .. Universal virtual TM .. SAT solver .. 855A Computing MachineRepresenting Number conversion .. Floating-point components .. 893 TOY Your first TOY program .. Conditionals and loops .. Self-modifying code.

9 923 Machine-Language Calling a function .. Standard output .. Standard input .. Array processing .. Linked structures .. 943 TOY Virtual TOY virtual machine .. 967xiBuilding a Computing DeviceBoolean LogicBasic Circuit ModelCombinational CircuitsBasic logic gates .. 1014 Selection multiplexer .. 1024 Decoder .. 1021 Demultiplexer .. 1022 Multiplexer .. 1023 XOR .. 1024 Majority .. 1025 Odd parity .. 1026 Adder .. 1029 ALU .. 1033 Bus multiplexer .. 1036 Sequential CircuitsSR flip-flop .. 1050 Register bit ..1051 Register.. 1052 Memory bit .. 1056 Memory ..1057 Clock .. 1061 Digital Devices Program counter .. 1074 Control .. 1081 CPU .. 1086 CircuitsxiiiPrefaceTHE BASIS FOR EDUCATION IN THE last millennium was reading, writing, and arith-metic ; now it is reading, writing, and computing.

10 Learning to program is an essential part of the education of every student in the sciences and engineering. Beyond direct applications, it is the first step in understanding the nature of com-puter science s undeniable impact on the modern world. This book aims to teach programming to those who need or want to learn it, in a scientific primary goal is to empower students by supplying the experience and basic tools necessary to use computation effectively. Our Approach is to teach stu-dents that composing a program is a natural, satisfying, and creative experience. We progressively introduce essential concepts, embrace classic applications from applied mathematics and the sciences to illustrate the concepts, and provide op-portunities for students to write programs to solve engaging problems. We seek also to demystify computation for students and to build awareness about the sub-stantial intellectual underpinnings of the field of Computer science.