Computer Science: An Interdisciplinary Approach

Table of Contents

Preface xiii

Chapter 1: Elements of Programming 1

1.1 Your First Program 2

1.2 Built-in Types of Data 14

1.3 Conditionals and Loops 50

1.4 Arrays 90

1.5 Input and Output 126

1.6 Case Study: Random Web Surfer 170

Chapter 2: Functions and Modules 191

2.1 Defining Functions 192

2.2 Libraries and Clients 226

2.3 Recursion 262

2.4 Case Study: Percolation 300

Chapter 3: Object-Oriented Programming 329

3.1 Using Data Types 330

3.2 Creating Data Types 382

3.3 Designing Data Types 428

3.4 Case Study: N-Body Simulation 478

Chapter 4: Algorithms and Data Structures 493

4.1 Performance 494

4.2 Sorting and Searching 532

4.3 Stacks and Queues 566

4.4 Symbol Tables 624

4.5 Case Study: Small-World Phenomenon 670

Chapter 5: Theory of Computing 715

5.1 Formal Languages 718

5.2 Turing Machines 766

5.3 Universality 786

5.4 Computability 806

5.5 Intractability 822

Chapter 6: A Computing Machine 873

6.1 Representing Information 874

6.2 TOY Machine 906

6.3 Machine-Language Programming 930

6.4 TOY Virtual Machine 958

Chapter 7: Building a Computing Device 985

7.1 Boolean Logic 986

7.2 Basic Circuit Model 1002

7.3 Combinational Circuits 1012

7.4 Sequential Circuits 1048

7.5 Digital Devices 1070

Context 1093

Glossary 1097

Index 1107

APIs 1139