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

Explore a preview version of Computer Science: An Interdisciplinary Approach right now.

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from 200+ publishers.

Start your free trial

Book description

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

    Table of contents

    1. About This E-Book
    2. Title Page
    3. Copyright Page
    4. Dedication Page
    5. Contents
    6. Programs
    7. Circuits
    8. Preface
      1. Coverage
      2. Use in the Curriculum
      3. Prerequisites
      4. Goals
      5. Online lectures
      6. Booksite
      7. Acknowledgments
    9. 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
    10. 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
    11. 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
    12. 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
    13. 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
    14. 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
    15. 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
    16. 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
    17. Glossary
    18. Index
    19. APIs
    20. 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