Computer Science: An Interdisciplinary Approach

Computer Science: An Interdisciplinary Approach

by Robert Sedgewick, Kevin Wayne
Released June 2016
Publisher(s): Addison-Wesley Professional
ISBN: 9780134076461

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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

Table of contents

  1. Cover Page
  2. About This E-Book
  3. Title Page
  4. Copyright Page
  5. Dedication Page
  6. Contents
  7. Programs
  8. Circuits
  9. Preface
    1. Coverage
    2. Use in the Curriculum
    3. Prerequisites
    4. Goals
    5. Online lectures
    6. Booksite
    7. Acknowledgments
  10. Chapter One. Elements of Programming
    1. 1.1 Your First Program
      1. Programming in Java
      2. Input and output
    2. Q&A
    3. Exercises
    4. 1.2 Built-in Types of Data
      1. Terminology
      2. Characters and strings
      3. Integers
      4. Floating-point numbers
      5. Booleans
      6. Comparisons
      7. Library methods and APIs
      8. Type conversion
      9. Summary
    5. Q&A (Strings)
    6. Q&A (Integers)
    7. Q&A (Floating-Point Numbers)
    8. Q&A (Variables and Expressions)
    9. Exercises
    10. Creative Exercises
    11. 1.3 Conditionals and Loops
      1. If statements
      2. While loops
      3. For loops
      4. Nesting
      5. Applications
      6. Other conditional and loop constructs
      7. Infinite loops
      8. Summary
    12. Q&A
    13. Exercises
    14. Creative Exercises
    15. 1.4 Arrays
      1. Arrays in Java
      2. Coupon collector
      3. Sieve of Eratosthenes
      4. Two-dimensional arrays
      5. Example: self-avoiding random walks
      6. Summary
    16. Q&A
    17. Exercises
    18. Creative Exercises
    19. 1.5 Input and Output
      1. Bird’s-eye view
      2. Standard output
      3. Standard input
      4. Redirection and piping
      5. Standard drawing
      6. Standard audio
      7. Summary
    20. Q&A
    21. Exercises
    22. Creative Exercises
    23. 1.6 Case Study: Random Web Surfer
      1. Input format
      2. Transition matrix
      3. Simulation
      4. Mixing a Markov chain
      5. Lessons
    24. Exercises
    25. Creative Exercises
  11. Chapter Two. Functions and Modules
    1. 2.1 Defining Functions
      1. Static methods
      2. Implementing mathematical functions
      3. Using static methods to organize code
      4. Passing arguments and returning values
      5. Example: superposition of sound waves
    2. Q&A
    3. Exercises
    4. Creative Exercises
    5. 2.2 Libraries and Clients
      1. Using static methods in other programs
      2. Libraries
      3. Random numbers
      4. Input and output for arrays
      5. Iterated function systems
      6. Statistics
      7. Modular programming
    6. Q&A
    7. Exercises
    8. Creative Exercises
    9. 2.3 Recursion
      1. Your first recursive program
      2. Mathematical induction
      3. Euclid’s algorithm
      4. Towers of Hanoi
      5. Function-call trees
      6. Exponential time
      7. Gray codes
      8. Recursive graphics
      9. Brownian bridge
      10. Pitfalls of recursion
      11. Dynamic programming
      12. Perspective
    10. Q&A
    11. Exercises
    12. Creative Exercises
    13. 2.4 Case Study: Percolation
      1. Percolation
      2. Basic scaffolding
      3. Vertical percolation
      4. Testing
      5. Estimating probabilities
      6. Recursive solution for percolation
      7. Adaptive plot
      8. Lessons
    14. Q&A
    15. Exercises
    16. Creative Exercises
  12. Chapter Three. Object-Oriented Programming
    1. 3.1 Using Data Types
      1. Basic definitions
      2. String-processing application: genomics
      3. Color
      4. Digital image processing
      5. Input and output revisited
      6. Properties of reference types
    2. Q&A
    3. Exercises
    4. Creative Exercises
    5. 3.2 Creating Data Types
      1. Basic elements of a data type
      2. Stopwatch
      3. Histogram
      4. Turtle graphics
      5. Complex numbers
      6. Mandelbrot set
      7. Commercial data processing
    6. Q&A
    7. Exercises
    8. Creative Exercises
    9. 3.3 Designing Data Types
      1. Designing APIs
      2. Encapsulation
      3. Immutability
      4. Example: spatial vectors
      5. Interface inheritance (subtyping)
      6. Implementation inheritance (subclassing)
      7. Application: data mining
      8. Design by contract
    10. Q&A
    11. Exercises
    12. Data-Type Design Exercises
    13. Creative Exercises
    14. 3.4 Case Study: N-Body Simulation
      1. N-body simulation
    15. Q&A
    16. Exercises
    17. Creative Exercises
  13. Chapter Four. Algorithms and Data Structures
    1. 4.1 Performance
      1. Scientific method
      2. Observations
      3. Hypotheses
      4. Order-of-growth classifications
      5. Predictions
      6. Caveats
      7. Performance guarantees
      8. Memory
      9. Perspective
    2. Q&A
    3. Exercises
    4. Creative Exercises
    5. 4.2 Sorting and Searching
      1. Binary search
      2. Insertion sort
      3. Mergesort
      4. Application: frequency counts
      5. Lessons
    6. Q&A
    7. Exercises
    8. Creative Exercises
    9. 4.3 Stacks and Queues
      1. Pushdown stacks
      2. Array implementation
      3. Linked lists
      4. Resizing arrays
      5. Parameterized data types
      6. FIFO queues
      7. Queue applications
      8. Resource allocation
    10. Q&A
    11. Exercises
    12. Linked-List Exercises
    13. Creative Exercises
    14. 4.4 Symbol Tables
      1. API
      2. Symbol-table clients
      3. Elementary symbol-table implementations
      4. Hash tables
      5. Binary search trees
      6. Performance characteristics of BSTs
      7. Traversing a BST
      8. Ordered symbol table operations
      9. Set data type
      10. Perspective
    15. Q&A
    16. Exercises
    17. Binary Tree Exercises
    18. Creative Exercises
    19. 4.5 Case Study: Small-World Phenomenon
      1. Graphs
      2. Graph data type
      3. Graph client example
      4. Shortest paths in graphs
      5. Small-world graphs
      6. Lessons
    20. Q&A
    21. Exercises
    22. Creative Exercises
  14. Chapter Five. Theory of Computing
    1. 5.1 Formal Languages
      1. Basic definitions
      2. Regular languages
      3. Generalized REs
      4. Applications
      5. Abstract machines
      6. Deterministic finite-state automata
      7. Java implementation of DFAs
      8. Nondeterminism
      9. Kleene’s theorem
      10. Applications of Kleene’s theorem
      11. Summary
    2. Q&A
    3. Exercises
    4. Creative Exercises
    5. 5.2 Turing Machines
      1. Turing machine model
      2. Universal virtual Turing machine
    6. Q&A
    7. Exercises
    8. Creative Exercises
    9. 5.3 Universality
      1. Algorithms
      2. Programs that process programs
      3. Church–Turing Thesis
      4. Variations on the TM model
      5. Universal models
    10. Q&A
    11. Creative Exercises
    12. 5.4 Computability
      1. Context: Hilbert’s program
      2. Warmup: liar’s paradox
      3. The halting problem
      4. Reduction
      5. More examples of unsolvable problems
      6. Implications
    13. Q&A
    14. Exercises
    15. Creative Exercises
    16. 5.5 Intractability
      1. Overview
      2. Examples
      3. Satisfiability
      4. Search problems
      5. The main question
      6. Polynomial-time reductions
      7. NP-completeness
      8. Proving problems to be NP-complete
      9. Coping with NP-completeness
    17. Q&A
    18. Exercises
    19. Creative Exercises
  15. Chapter Six. A Computing Machine
    1. 6.1 Representing Information
      1. Binary and Hexadecimal
      2. Parsing and string representations
      3. Integer arithmetic
      4. Negative numbers
      5. Real numbers
      6. Java code for manipulating bits
      7. Characters
      8. Summary
    2. Q&A
    3. Exercises
    4. Creative Exercises
    5. 6.2 TOY Machine
      1. Brief historical note
      2. TOY components
      3. Fetch–increment–execute cycle
      4. Instructions
      5. Your first TOY program
      6. Operating the machine
      7. Conditionals and loops
      8. Stored-program computing
      9. Von Neumann machines
    6. Q&A
    7. Exercises
    8. 6.3 Machine-Language Programming
      1. Functions
      2. Standard output
      3. Standard input
      4. Arrays
      5. Linked structures
      6. Why learn machine-language programming?
    9. Q&A
    10. Exercises
    11. Creative Exercises
    12. 6.4 TOY Virtual Machine
      1. Booting and dumping
      2. A note of caution
      3. Programs that process programs
      4. TOY in Java
      5. The TOY family of imaginary computers
    13. Q&A
    14. Exercises
    15. Creative Exercises
  16. Chapter Seven. Building a Computing Device
    1. 7.1 Boolean Logic
      1. Boolean functions
      2. An application
      3. Boolean functions of three or more variables
    2. Exercises
    3. Creative Exercises
    4. 7.2 Basic Circuit Model
      1. Wires
      2. Controlled switches
      3. Circuits
      4. Logical design and the real world
    5. Q&A
    6. Exercises
    7. 7.3 Combinational Circuits
      1. Gates
      2. Building a circuit from gates
      3. Decoders, demuxes, and muxes
      4. Sum-of-products circuits
      5. Adder
      6. Arithmetic logic unit (ALU)
      7. Modules and buses
      8. Layers of abstraction
    8. Q&A
    9. Exercises
    10. Creative Exercises
    11. 7.4 Sequential Circuits
      1. Elementary feedback circuits
      2. Flip-flops
      3. Registers
      4. Memory
      5. Clock
      6. Summary
    12. Q&A
    13. Exercises
    14. Creative Exercises
    15. 7.5 Digital Devices
      1. TOY-8
      2. Warmup
      3. TOY-8 CPU organization and connections
      4. Control
      5. Example: A TOY-8 program
      6. Perspective
    16. Q&A
    17. Exercises
    18. Creative Exercises
  17. Context
    1. Java libraries
    2. Programming environments
    3. Scientific computing
    4. Apps and cloud computing
    5. Computer systems
    6. Theory of computing
    7. Machine learning
  18. Glossary
  19. Index
  20. APIs
  21. Code Snippets

Product information

  • Title: Computer Science: An Interdisciplinary Approach
  • Author(s): Robert Sedgewick, Kevin Wayne
  • Release date: June 2016
  • Publisher(s): Addison-Wesley Professional
  • ISBN: 9780134076461