Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo
Introduction to the Art of Programming Using Scala

Book Description

With its flexibility for programming both small and large projects, Scala is an ideal language for teaching beginning programming. Yet there are no textbooks on Scala currently available for the CS1/CS2 levels. Introduction to the Art of Programming Using Scala presents many concepts from CS1 and CS2 using a modern, JVM-based language that works well for both programming in the small and programming in the large.

The book progresses from true programming in the small to more significant projects later, leveraging the full benefits of object orientation. It first focuses on fundamental problem solving and programming in the small using the REPL and scripting environments. It covers basic logic and problem decomposition and explains how to use GUIs and graphics in programs. The text then illustrates the benefits of object-oriented design and presents a large collection of basic data structures showing different implementations of key ADTs along with more atypical data structures. It also introduces multithreading and networking to provide further motivating examples.

By using Scala as the language for both CS1 and CS2 topics, this textbook gives students an easy entry into programming small projects as well as a firm foundation for taking on larger-scale projects. Many student and instructor resources are available at www.programmingusingscala.net

Table of Contents

  1. Preliminaries
  2. Acknowledgments
  3. Preface
    1. To the Student
      1. Using this Book
      2. Book Website
    2. To the Instructor
      1. Using this Book
      1. Figure 1
  4. Part I Introductory Concepts
    1. Chapter 1 Basics of Computers, Computing, and Programming
      1. 1.1 History
      2. 1.2 Hardware
      3. 1.3 Software
      4. 1.4 Nature of Programming
      5. 1.5 Programming Paradigms
        1. 1.5.1 Imperative Programming
        2. 1.5.2 Functional Programming
        3. 1.5.3 Object-Oriented Programming
        4. 1.5.4 Logic Programming
        5. 1.5.5 Nature of Scala
      6. 1.6 End of Chapter Material
        1. 1.6.1 Summary of Concepts
        2. 1.6.2 Exercises
        3. 1.6.3 Projects
        1. Figure 1.1
    2. Chapter 2 Getting to Know the Tools
      1. 2.1 Unix/Linux (includes Mac OS X)
        1. 2.1.1 Command-Line
          1. 2.1.1.1 Files and Directories
          2. 2.1.1.2 Aside
          3. 2.1.1.3 Helpful Tips
          4. 2.1.1.4 Permissions
          5. 2.1.1.5 Compression/Archiving
          6. 2.1.1.6 Remote
          7. 2.1.1.7 Other Commands
        2. 2.1.2 I/O Redirection
        3. 2.1.3 Text Editors (vi/vim)
      2. 2.2 Windows
        1. 2.2.1 Command-Line
          1. 2.2.1.1 Files and Directories
        2. 2.2.2 Text Editors
          1. 2.2.2.1 Edit
          2. 2.2.2.2 Notepad
          3. 2.2.2.3 Others
        3. 2.2.3 Other Commands
      3. 2.3 Scala Tools
      4. 2.4 End of Chapter Material
        1. 2.4.1 Summary of Concepts
        2. 2.4.2 Exercises
        1. Figure 2.1
        2. Figure 2.2
        3. Figure 2.3
        4. Figure 2.4
    3. Chapter 3 Scala Basics
      1. 3.1 Expressions, Types, and Basic Math
      2. 3.2 Objects and Methods
      3. 3.3 Other Basic Types
      4. 3.4 Back to the Numbers
        1. 3.4.1 Binary Arithmetic
        2. 3.4.2 Negative Numbers in Binary
        3. 3.4.3 Other Integer Types
        4. 3.4.4 Octal and Hexadecimal
        5. 3.4.5 Non-Integer Numbers
      5. 3.5 The math Object
      6. 3.6 Details of Char and String
      7. 3.7 Naming Values and Variables
      8. 3.8 Sequential Execution
        1. 3.8.1 Comments
      9. 3.9 A Tip for Learning to Program
      10. 3.10 End of Chapter Material
        1. 3.10.1 Problem-Solving Approach
        2. 3.10.2 Summary of Concepts
        3. 3.10.3 Self-Directed Study
        4. 3.10.4 Exercises
        1. Figure 3.1
        2. Figure 3.2
        1. Table 3.1
        2. Table 3.2
        3. Table 3.3
    4. Chapter 4 Conditionals
      1. 4.1 Motivating Example
      2. 4.2 The if Expression
      3. 4.3 Comparisons
      4. 4.4 Boolean Logic
      5. 4.5 Bigger Expressions
      6. Bit-wise Arithmetic
      7. 4.6 End of Chapter Material
        1. 4.6.1 Problem-Solving Approach
        2. 4.6.2 Summary of Concepts
        3. 4.6.3 Self-Directed Study
        4. 4.6.4 Exercises
        5. 4.6.5 Projects
        1. Table 4.1
        2. Table 4.2
        3. Table 4.3
        4. Table 4.4
    5. Chapter 5 Functions
      1. 5.1 Motivating Example
      2. 5.2 Function Refresher
      3. 5.3 Making and Using Functions
      4. 5.4 Problem Decomposition
      5. 5.5 Function Literals
      6. 5.6 Non-Functional Functions/Procedures
      7. 5.7 type Declarations
      8. 5.8 Putting it Together
      9. 5.9 End of Chapter Material
        1. 5.9.1 Problem-Solving Approach
        2. 5.9.2 Summary of Concepts
        3. 5.9.3 Self-Directed Study
        4. 5.9.4 Exercises
        5. 5.9.5 Projects
        1. Figure 5.1
        2. Figure 5.2
    6. Chapter 6 Recursion for Iteration
      1. 6.1 Basics of Recursion
      2. 6.2 Writing Recursion
      3. 6.3 User Input
      4. 6.4 Abstraction
      5. 6.5 Matching
      6. 6.6 Putting it Together
      7. 6.7 Looking Ahead
      8. 6.8 End of Chapter Material
        1. 6.8.1 Problem-Solving Approach
        2. 6.8.2 Summary of Concepts
        3. 6.8.3 Self-Directed Study
        4. 6.8.4 Exercises
        5. 6.8.5 Projects
        1. Figure 6.1
    7. Chapter 7 Arrays and Lists in Scala
      1. 7.1 Making Arrays
      2. 7.2 Using Arrays
      3. 7.3 Lists
      4. 7.4 Standard Methods
        1. 7.4.1 Basic Methods
        2. 7.4.2 Higher-Order Methods
        3. 7.4.3 Combinatorial/Iterator Methods
      5. 7.5 A World of Types
        1. 7.5.1 The Option Type
        2. 7.5.2 Parametric Functions
        3. 7.5.3 Subtyping
      6. 7.6 Variable Length Argument Lists
      7. 7.7 Mutability and Aliasing
      8. 7.8 Basic Argument Passing
      9. 7.9 Pass-By-Name
      10. 7.10 Fill and Tabulate
      11. 7.11 Complete Grades Script/Software Development
      12. 7.12 End of Chapter Material
        1. 7.12.1 Problem-Solving Approach
        2. 7.12.2 Summary of Concepts
        3. 7.12.3 Self-Directed Study
        4. 7.12.4 Exercises
        5. 7.12.5 Projects
        1. Figure 7.1
        2. Figure 7.2
        3. Figure 7.3
        4. Figure 7.4
        5. Figure 7.5
        6. Figure 7.6
    8. Chapter 8 Loops
      1. 8.1 while Loop
      2. 8.2 do-while Loop
      3. 8.3 for Loop
        1. 8.3.1 Range Type
        2. 8.3.2 yield
        3. 8.3.3 if Guards
        4. 8.3.4 Multiple Generators
        5. 8.3.5 Patterns in for Loops
        6. 8.3.6 Variable Declarations
      4. 8.4 Multidimensional Arrays
      5. 8.5 Testing
      6. 8.6 Putting it Together
      7. 8.7 End of Chapter Material
        1. 8.7.1 Problem-Solving Approach
        2. 8.7.2 Summary of Concepts
        3. 8.7.3 Self-Directed Study
        4. 8.7.4 Exercises
        5. 8.7.5 Projects
    9. Chapter 9 Text Files
      1. 9.1 I/O Redirection
      2. 9.2 Packages and import Statements
      3. 9.3 Reading from Files
        1. 9.3.1 Iterators
        2. 9.3.2 String split Method
        3. 9.3.3 Reading from Other Things
        4. 9.3.4 Other Options (Java Based)
      4. 9.4 Writing to File
        1. 9.4.1 Appending to File
      5. 9.5 Use Case: Simple Encryption
        1. 9.5.1 Command-Line Arguments
        2. 9.5.2 Mapping a File
        3. 9.5.3 Character Offset
        4. 9.5.4 Alphabet Flip
        5. 9.5.5 Key Word
        6. 9.5.6 Putting it Together
        7. 9.5.7 Primes and Real Cryptography
      6. 9.6 End of Chapter Material
        1. 9.6.1 Summary of Concepts
        2. 9.6.2 Self-Directed Study
        3. 9.6.3 Exercises
        4. 9.6.4 Projects
    10. Chapter 10 Case Classes
      1. 10.1 User-Defined Types
      2. 10.2 Case Classes
        1. 10.2.1 Making Objects
        2. 10.2.2 Accessing Elements
        3. 10.2.3 Named and Default Arguments (Advanced)
        4. 10.2.4 The copy Method
        5. 10.2.5 Case Class Patterns
      3. 10.3 Mutable Classes
      4. 10.4 Putting it Together
      5. 10.5 End of Chapter Material
        1. 10.5.1 Summary of Concepts
        2. 10.5.2 Self-Directed Study
        3. 10.5.3 Exercises
        4. 10.5.4 Projects
    11. Chapter 11 GUIs
      1. 11.1 GUI Libraries and History
      2. 11.2 GUI Components
        1. 11.2.1 Frames and Windows
        2. 11.2.2 Components
        3. 11.2.3 Panels and Panes
        4. 11.2.4 Menus
        5. 11.2.5 Tooltips
      3. 11.3 Basic Interactivity
        1. 11.3.1 Partial Functions
        2. 11.3.2 Publishers and Reactors
        3. 11.3.3 Mnemonics
      4. 11.4 FileChooser
      5. 11.5 Tables
        1. 11.5.1 Table Actions
        2. 11.5.2 Table Models
      6. 11.6 Putting it Together
      7. 11.7 End of Chapter Material
        1. 11.7.1 Summary of Concepts
        2. 11.7.2 Self-Directed Study
        3. 11.7.3 Exercises
        4. 11.7.4 Projects
        1. Figure 11.1
        2. Figure 11.2
        3. Figure 11.3
    12. Chapter 12 Graphics
      1. 12.1 Custom-Drawn Panels
      2. 12.2 java.awt.Graphics2D
        1. 12.2.1 Shapes
        2. 12.2.2 Settings
          1. 12.2.2.1 Paint
          2. 12.2.2.2 Stroke
          3. 12.2.2.3 Font
          4. 12.2.2.4 Clip
          5. 12.2.2.5 Transform
        3. 12.2.3 Affine Transforms
      3. 12.3 Images
        1. 12.3.1 BufferedImage
        2. 12.3.2 Reading and Writing Images
        3. 12.3.3 Double Buffering
        4. 12.3.4 Revisiting TexturePaint
      4. 12.4 Other Events
        1. 12.4.1 Mouse Events
        2. 12.4.2 Keyboard Events
      5. 12.5 Animation with Timer
      6. 12.6 Putting it Together
      7. 12.7 End of Chapter Material
        1. 12.7.1 Summary of Concepts
        2. 12.7.2 Exercises
        3. 12.7.3 Projects
        1. Figure 12.1
        2. Figure 12.2
        3. Figure 12.3
        4. Figure 12.4
        5. Figure 12.5
        6. Figure 12.6
        7. Figure 12.7
    13. Chapter 13 Sorting and Searching
      1. 13.1 Basic Comparison Sorts
        1. 13.1.1 Bubble Sort
        2. 13.1.2 Selection Sort (Min/Max)
        3. 13.1.3 Insertion Sort
        4. 13.1.4 Testing and Verifying Sorts
        5. 13.1.5 Sort Visualization
        6. 13.1.6 Order Analysis
        7. 13.1.7 Shell Sort (Diminishing Gap Sort)
      2. 13.2 Searching
        1. 13.2.1 Sequential Search (Linear Search)
        2. 13.2.2 Binary Search
      3. 13.3 Performance and Timing
      4. 13.4 Classifying Bugs
      5. 13.5 Memory Layout
      6. 13.6 Sorting/Searching with case classes
      7. 13.7 Putting it Together
      8. 13.8 End of Chapter Material
        1. 13.8.1 Summary of Concepts
        2. 13.8.2 Exercises
        3. 13.8.3 Projects
        1. Table 13.1
    14. Chapter 14 XML
      1. 14.1 Description of XML
        1. 14.1.1 Tags
        2. 14.1.2 Elements
        3. 14.1.3 Attributes
        4. 14.1.4 Content
        5. 14.1.5 Special Characters
        6. 14.1.6 Comments
        7. 14.1.7 Overall Format
        8. 14.1.8 Comparison to Flat File
          1. 14.1.8.1 Flexibility in XML
      2. 14.2 XML in Scala
        1. 14.2.1 Loading XML
        2. 14.2.2 Parsing XML
        3. 14.2.3 Building XML
        4. 14.2.4 Writing XML to File
        5. 14.2.5 XML Patterns
      3. 14.3 Putting it Together
      4. 14.4 End of Chapter Material
        1. 14.4.1 Summary of Concepts
        2. 14.4.2 Self-Directed Study
        3. 14.4.3 Exercises
        4. 14.4.4 Projects
    15. Chapter 15 Recursion
      1. 15.1 Power of Recursion
      2. 15.2 Fibonacci Numbers
      3. 15.3 Permutations
      4. 15.4 Towers of Hanoi
      5. 15.5 Mazes
      6. 15.6 Sorts
        1. 15.6.1 Divide and Conquer Sorts
          1. 15.6.1.1 Merge Sort
          2. 15.6.1.2 Quicksort
      7. 15.7 Putting it Together
      8. 15.8 End of Chapter Material
        1. 15.8.1 Summary of Concepts
        2. 15.8.2 Exercises
        3. 15.8.3 Projects
        1. Figure 15.1
        2. Figure 15.2
  5. Part II Object-Orientation, Abstraction, and Data Structures
    1. Chapter 16 Object-Orientation
      1. 16.1 Basics of Object-Orientation
        1. 16.1.1 Methods and Members
          1. 16.1.1.1 Parameters as Members
          2. 16.1.1.2 Visibility
        2. 16.1.2 this Keyword
        3. 16.1.3 Encapsulation/Separating Interface from Implementation
        4. 16.1.4 Special Methods
          1. 16.1.4.1 Operator Methods
          2. 16.1.4.2 Unary Operators
          3. 16.1.4.3 Property Assignment Methods
          4. 16.1.4.4 The apply Method
          5. 16.1.4.5 The update Method
          6. 16.1.4.6 Overloading Methods
          7. 16.1.4.7 Vector Example
        5. 16.1.5 object Declarations
          1. 16.1.5.1 Applications
          2. 16.1.5.2 Introduction to Companion Objects
        6. 16.1.6 Object Decomposition
      2. 16.2 Revisiting the API
      3. 16.3 Meaning of case classes
      4. 16.4 import Options
      5. 16.5 End of Chapter Material
        1. 16.5.1 Summary of Concepts
        2. 16.5.2 Exercises
        3. 16.5.3 Projects
        1. Figure 16.1
        1. Table 16.1
    2. Chapter 17 Bigger Programs/New Tools
      1. 17.1 Eclipse IDE
      2. 17.2 Concurrent Versions System (CVS)
        1. 17.2.1 Making the Repository
        2. 17.2.2 Set-up in Eclipse
        3. 17.2.3 Getting Access on Other Systems
        4. 17.2.4 Repository Usage and Rules
      3. 17.3 Scaladoc Comments
      4. 17.4 End of Chapter Material
        1. 17.4.1 Summary of Concepts
        2. 17.4.2 Exercises
        3. 17.4.3 Projects
        1. Figure 17.1
        2. Figure 17.2
        3. Figure 17.3
        4. Figure 17.4
        5. Figure 17.5
        6. Figure 17.6
        7. Figure 17.7
        8. Figure 17.8
    3. Chapter 18 A Project (Drawing Program)
      1. 18.1 Software Development Stages
      2. 18.2 Analysis
      3. 18.3 Design
      4. 18.4 Making Packages
      5. 18.5 Project Analysis and Design
      6. 18.6 Implementing the GUI
      7. 18.7 End of Chapter Material
        1. 18.7.1 Summary of Concepts
        2. 18.7.2 Exercises
        3. 18.7.3 Projects
        1. Figure 18.1
        2. Figure 18.2
        3. Figure 18.3
        4. Figure 18.4
        5. Figure 18.5
    4. Chapter 19 Abstraction and Polymorphism
      1. 19.1 Polymorphism
      2. 19.2 Inclusion Polymorphism (Inheritance and Subtyping)
        1. 19.2.1 private Visibility and Inheritance
        2. 19.2.2 Protected Visibility
        3. 19.2.3 Calling Methods on the Supertype
        4. 19.2.4 Anonymous Classes
        5. 19.2.5 Abstract Classes
        6. 19.2.6 traits
        7. 19.2.7 final
        8. 19.2.8 Method Resolution
        9. 19.2.9 Inheriting from Function Types
      3. 19.3 Inheritance in the Project
        1. 19.3.1 Drawables
        2. 19.3.2 Integration with Drawing
      4. 19.4 Parametric Polymorphism
        1. 19.4.1 Parametric Types
        2. 19.4.2 Parametric Functions and Methods
        3. 19.4.3 Type Bounds
      5. 19.5 End of Chapter Material
        1. 19.5.1 Summary of Concepts
        2. 19.5.2 Exercises
        3. 19.5.3 Projects
        1. Figure 19.1
        2. Figure 19.2
        3. Figure 19.3
        4. Figure 19.4
        5. Figure 19.5
        6. Figure 19.6
    5. Chapter 20 Other Collection Types
      1. 20.1 The scala.collection Packages
        1. 20.1.1 scala.collection.immutable
        2. 20.1.2 scala.collection.mutable
      2. 20.2 Sets
        1. 20.2.1 Running Through Sets
        2. 20.2.2 Mutable vs. Immutable
        3. 20.2.3 Using a Set
      3. 20.3 Maps
        1. 20.3.1 Looping Through a Map
        2. 20.3.2 Using Maps
      4. 20.4 Buffers
      5. 20.5 Collections as Functions
      6. 20.6 Project Integration
        1. 20.6.1 Commands
        2. 20.6.2 Adding Drawables
      7. 20.7 End of Chapter Material
        1. 20.7.1 Summary of Concepts
        2. 20.7.2 Exercises
        3. 20.7.3 Projects
        1. Figure 20.1
        2. Figure 20.2
        3. Figure 20.3
    6. Chapter 21 Multithreading and Concurrency
      1. 21.1 The Multicore Future
      2. 21.2 Basic Threads
        1. 21.2.1 Problems with Threads
          1. 21.2.1.1 Race Conditions
          2. 21.2.1.2 Deadlock
        2. 21.2.2 Synchronization
        3. 21.2.3 Wait/Notify
        4. 21.2.4 Other Thread Methods
      3. 21.3 Concurrency Library
        1. 21.3.1 Executors and Executor Services
        2. 21.3.2 Callable and Futures
        3. 21.3.3 Parallel Data Structures
          1. 21.3.3.1 Shared Barriers
          2. 21.3.3.2 The Exchange
          3. 21.3.3.3 Assembly Line
          4. 21.3.3.4 Ticketed Passengers
          5. 21.3.3.5 Other Threadsafe Types
        4. 21.3.4 Atomic (java.util.concurrent.atomic)
        5. 21.3.5 Locks (java.util.concurrent.locks)
      4. 21.4 Parallel Collections
      5. 21.5 Introduction to Scala Actors
      6. 21.6 Multithreaded Mandelbrot (Project Integration)
      7. 21.7 Multithreading in GUIs
      8. 21.8 Animated Bouncing Balls (Project Integration)
      9. 21.9 End of Chapter Material
        1. 21.9.1 Summary of Concepts
        2. 21.9.2 Exercises
        3. 21.9.3 Projects
        1. Figure 21.1
        2. Figure 21.2
        3. Figure 21.3
    7. Chapter 22 Stream I/O
      1. 22.1 The java.io Package
      2. 22.2 Streams for Files
      3. 22.3 Exceptions
        1. 22.3.1 try-catch-finally
        2. 22.3.2 Effect of Exceptions
        3. 22.3.3 Loan Pattern
      4. 22.4 Decorating Streams
        1. 22.4.1 Buffering
        2. 22.4.2 Binary Data
        3. 22.4.3 Serialization
          1. 22.4.3.1 Binary Serialization
          2. 22.4.3.2 XML Serialization
      5. 22.5 Saving Drawings (Project Integration)
      6. 22.6 End of Chapter Material
        1. 22.6.1 Summary of Concepts
        2. 22.6.2 Exercises
        3. 22.6.3 Projects
    8. Chapter 23 Networking
      1. 23.1 TCP and UDP
      2. 23.2 Sockets
        1. 23.2.1 TCP Sockets
        2. 23.2.2 UDP Sockets
        3. 23.2.3 Streams from Sockets
      3. 23.3 URLs
      4. 23.4 Remote Method Invocation (RMI)
      5. 23.5 Collaborative Drawing (Project Integration)
      6. 23.6 End of Chapter Material
        1. 23.6.1 Summary of Concepts
        2. 23.6.2 Exercises
        3. 23.6.3 Projects
        1. Figure 23.1
        2. Figure 23.2
        3. Figure 23.3
    9. Chapter 24 Stacks and Queues
      1. 24.1 Abstract Data Types (ADTs)
      2. 24.2 Operations on Stacks and Queues
      3. 24.3 Real Meaning of O
      4. 24.4 O(1) Requirement
      5. 24.5 Array-Based Stack
      6. 24.6 Array-Based Queue
      7. 24.7 Unit Tests
        1. 24.7.1 Setup
        2. 24.7.2 Writing Tests
        3. 24.7.3 Test Suites
        4. 24.7.4 Test-Driven Development
      8. 24.8 RPN Calculator
      9. 24.9 End of Chapter Material
        1. 24.9.1 Summary of Concepts
        2. 24.9.2 Exercises
        3. 24.9.3 Projects
        1. Figure 24.1
        2. Figure 24.2
        3. Figure 24.3
        4. Figure 24.4
        5. Figure 24.5
    10. Chapter 25 Linked Lists
      1. 25.1 The List/Seq ADT
      2. 25.2 Nature of Arrays
      3. 25.3 Nature of Linked Lists
      4. 25.4 Mutable Singly-Linked List
        1. 25.4.1 Implementing mutable.Buffer
        2. 25.4.2 Iterators
      5. 25.5 Mutable Doubly-Linked List
      6. 25.6 Immutable Singly-Linked List
      7. 25.7 Linked List-Based Stacks and Queues
        1. 25.7.1 Linked List-Based Stack
        2. 25.7.2 Linked List-Based Queue
      8. 25.8 End of Chapter Material
        1. 25.8.1 Summary of Concepts
        2. 25.8.2 Exercises
        3. 25.8.3 Projects
        1. Figure 25.1
    11. Chapter 26 Priority Queues
      1. 26.1 Two Approaches
        1. 26.1.1 Searching by Priority
        2. 26.1.2 Sorted Linked List
        3. 26.1.3 Problems with Arrays
      2. 26.2 Project Integration: Discrete Event Simulation
        1. 26.2.1 Cell Splitting
        2. 26.2.2 Collision Handling
      3. 26.3 End of Chapter Material
        1. 26.3.1 Summary of Concepts
        2. 26.3.2 Exercises
        3. 26.3.3 Projects
        1. Figure 26.1
    12. Chapter 27 Refactoring
      1. 27.1 Smells
      2. 27.2 Refactorings
        1. 27.2.1 Built-in Refactoring Methods
        2. 27.2.2 Introduce Null Object
        3. 27.2.3 Add and Remove Parameter
        4. 27.2.4 Cures for Switch Statements
        5. 27.2.5 Consolidate Conditional Expression
        6. 27.2.6 Convert Procedural Design to Objects
        7. 27.2.7 Encapsulate Collection
        8. 27.2.8 Push Down or Pull Up Field or Method
        9. 27.2.9 Substitute Algorithm
      3. 27.3 End of Chapter Material
        1. 27.3.1 Summary of Concepts
        2. 27.3.2 Exercises
        3. 27.3.3 Projects
    13. Chapter 28 Recursion
      1. 28.1 Refresher
      2. 28.2 Project Integration: A Maze
        1. 28.2.1 Revisiting the Basic Approach
        2. 28.2.2 Graphical Editing
        3. 28.2.3 Optimizing the Maze
      3. 28.3 Graph Traversals
      4. 28.4 Divide and Conquer
        1. 28.4.1 Merge Sort
        2. 28.4.2 Quicksort
        3. 28.4.3 Formula Parser
      5. 28.5 End of Chapter Material
        1. 28.5.1 Summary of Concepts
        2. 28.5.2 Exercises
        3. 28.5.3 Projects
    14. Chapter 29 Trees
      1. 29.1 General Trees
        1. 29.1.1 Implementations
        2. 29.1.2 Traversals
      2. 29.2 Project Integration: Formula Parsing
        1. 29.2.1 Formula Tree Traversals and In-order Traversal
      3. 29.3 Binary Search Trees: Binary Trees as Maps
        1. 29.3.1 Order Analysis
        2. 29.3.2 Immutable BSTs
      4. 29.4 End of Chapter Material
        1. 29.4.1 Summary of Concepts
        2. 29.4.2 Exercises
        3. 29.4.3 Projects
        1. Figure 29.1
        2. Figure 29.2
        3. Figure 29.3
        4. Figure 29.4
        5. Figure 29.5
        6. Figure 29.6
    15. Chapter 30 Regular Expressions and Context-Free Parsers
      1. 30.1 Chomsky Grammars
        1. 30.1.1 Regular Grammars
        2. 30.1.2 Context-Free Grammars
        3. 30.1.3 Context-Sensitive Grammars
        4. 30.1.4 Recursively Enumerable Grammars
      2. 30.2 Regular Expressions
        1. 30.2.1 Characters and Character Classes
        2. 30.2.2 Logical Operators and Capturing Groups
        3. 30.2.3 Greedy Quantifiers
        4. 30.2.4 Boundary Requirements
        5. 30.2.5 Using Regular Expressions in Code
        6. 30.2.6 Drawback of Regular Expressions
      3. 30.3 Context-Free Parsers
        1. 30.3.1 Default Output
        2. 30.3.2 Specified Output
      4. 30.4 Project Integration
      5. 30.5 End of Chapter Material
        1. 30.5.1 Summary of Concepts
        2. 30.5.2 Exercises
        3. 30.5.3 Projects
    16. Chapter 31 Spatial Trees
      1. 31.1 Spatial Data and Grids
      2. 31.2 Quadtrees and Octrees
      3. 31.3 kD-Trees
      4. 31.4 Efficient Bouncing Balls
      5. 31.5 End of Chapter Material
        1. 31.5.1 Summary of Concepts
        2. 31.5.2 Exercises
        3. 31.5.3 Projects
        1. Figure 31.1
        2. Figure 31.2
        3. Figure 31.3
    17. Chapter 32 Binary Heaps
      1. 32.1 Binary Heaps
        1. 32.1.1 Binary Heaps as Arrays
      2. 32.2 Heaps as Priority Queues
      3. 32.3 Heapsort
      4. 32.4 End of Chapter Material
        1. 32.4.1 Summary of Concepts
        2. 32.4.2 Exercises
        3. 32.4.3 Projects
        1. Figure 32.1
        2. Figure 32.2
        3. Figure 32.3
        4. Figure 32.4
        5. Figure 32.5
    18. Chapter 33 Direct Access Binary Files
      1. 33.1 Random Access Files
        1. 33.1.1 Fixed Record Length
        2. 33.1.2 Indexed Variable Record Length
      2. 33.2 Linked Structures in Files
      3. 33.3 End of Chapter Material
        1. 33.3.1 Summary of Concepts
        2. 33.3.2 Exercises
        3. 33.3.3 Projects
        1. Figure 33.1
        2. Figure 33.2
        3. Figure 33.3
        1. Table 33.1
    19. Chapter 34 Actors
      1. 34.1 Actor Model
      2. 34.2 scala.actors Package
        1. 34.2.1 The receive Method and Messages
        2. 34.2.2 react, loop, and loopWhile
      3. 34.3 Circuit Simulation
      4. 34.4 End of Chapter Material
        1. 34.4.1 Summary of Concepts
        2. 34.4.2 Exercises
        3. 34.4.3 Projects
        1. Figure 34.1
        2. Figure 34.2
    20. Chapter 35 Augmenting Trees
      1. 35.1 Augmentation of Trees
      2. 35.2 Balanced BSTs
        1. 35.2.1 Rotations
        2. 35.2.2 Implementation
      3. 35.3 Order-Statistic Trees: Trees as Sequences
      4. 35.4 Augmented Spatial Trees
      5. 35.5 End of Chapter Material
        1. 35.5.1 Summary of Concepts
        2. 35.5.2 Exercises
        3. 35.5.3 Projects
        1. Figure 35.1
        2. Figure 35.2
        3. Figure 35.3
    21. Chapter 36 Wrapping Up
      1. 36.1 What You Have Learned
      2. 36.2 The Possibilities/A Pet Project
        1. 36.2.1 General 2-D Application
        2. 36.2.2 3-D Application
        3. 36.2.3 Mobile
        4. 36.2.4 Web
        5. 36.2.5 GPGPU
        6. 36.2.6 AI, NLP, and Machine Learning
        7. 36.2.7 Open-Source and More
      3. 36.3 End of Chapter Material
        1. 36.3.1 Exercises
        2. 36.3.2 Projects
  6. Appendix A Quick Preview of Java
    1. A.1 Hello World
    2. A.2 Arrays, Primitives, and More
    3. A.3 File Names and Interfaces
    4. A.4 Constructors and @Override
    5. A.5 Generics and Polymorphism
    6. A.6 Lacking Functional Aspects
    7. A.7 Much More
  7. Appendix B Advanced Scala Concepts
    1. B.1 abstract type Members
    2. B.2 Enumerations
    3. B.3 implicits
      1. B.3.1 Basic implict Converstions
      2. B.3.2 Rules and Limits on implicits
      3. B.3.3 implicit Parameters
      4. B.3.4 The Meaning of <%
    4. B.4 sealed classes
    5. B.5 Covariant, Contravariant, and Invariant Types
    6. B.6 Extractors
      1. B.6.1 unapply
      2. B.6.2 unapplySeq
    7. B.7 lazy Member Data
    8. B.8 scala.collection.immutable.Stream
    9. B.9 Nested Types
    10. B.10 Self Types
    11. B.11 Making Executable JAR Files
  8. Appendix C Glossary
  9. Bibliography