Data Structures and Algorithms with Object-Oriented Design Patterns in C++
Data Structures and Algorithms with Object-Oriented Design Patterns in C++
ISBN: 0471241342
EAN: 2147483647
EAN: 2147483647
Year: 1998
Pages: 101
Pages: 101
Authors: Bruno R. Preiss
- No Title Found _Reports ask_page_thumbs.htm
- WebZIP Tasks
- WebZIP Task Summary
- Copyright Notice
- CV and Resume
- Website of Bruno R. Preiss
- Bruno s Home Page
- Opuses (Opera?)
- Contents
- Journal Articles
- From Design Patterns to Parallel Architecture Skeletons
- Effects of the Checkpoint Interval on Time and Space in Time Warp
- Optimal Memory Management for Time Warp Parallel Simulation
- Simulating Continuous Systems with Piecewise-Linear Signals Using Time Warp
- Short Packet Transfer Performance in Local Area Ring Networks
- A Nonuniform Detector Aperture for CT
- On the Transport of Charged Particles Through Spongy Materials
- Conference Papers
- Building Parallel Applications using Design Patterns
- Research
- Using Object-Oriented Techniques for Realizing Parallel Architectural Skeletons
- Issues in Joint Undergraduate Software Engineering Degree Program Design
- Architectural Skeletons: The Re-Usable Building-Blocks for Parallel Applications
- Design Patterns for the Data Structures and Algorithms Course
- The Parsimony Project: A Distributed Simulation Testbed in Java
- Memory Management Techniques for Time Warp on a Distributed Memory Machine
- An Algorithm for Speculative Parallel Execution of Rendezvous-Synchronized Simulation
- On the Performance of a Multi-Threaded RISC Architecture
- Selecting the Checkpoint Interval in Time Warp Parallel Simulation
- A Unifying Framework for Distributed Routing Algorithms
- Publications
- On the Trade-Off between Time and Space in Optimistic Parallel Discrete-Event Simulation
- Parallel Instance Discrete-Event Simulation Using a Vector Uniprocessor
- Multi-Threaded Pipelining in a RISC Processor
- Null Message Cancellation in Conservative Distributed Simulation
- Performance of Discrete Event Simulation on a Multiprocessor Using Optimistic and Conservative Synchronization
- The Impact of Lookahead on the Performance of Conservative Distributed Simulation
- The Role of Knowledge in Distributed Simulation
- The Yaddes Distributed Discrete Event Simulation Specification Language and Execution Environments
- A Unified Modeling Methodology for Performance Evaluation of Distributed Discrete Event Simulation Mechanisms
- Semi-Static Dataflow
- Books
- A Cache-based Message Passing Scheme for a Shared-bus Multiprocessor
- Data Flow on a Queue Machine
- Short-Packet Transfer Performance in Local Area Rings
- Patents
- Method, System and Apparatus For Provisioning Services to Subscribers in a Telecommunications Network
- Interactive Voice Response System and Method (IVR cisco)
- Telecommunication Architecture
- Strategy for Negotiation of Telecommunication Resources
- Method and System for Configuring Communication Resources
- Technical Reports
- Data Structures and Algorithms with Object-Oriented Design Patterns in C
- Transputer System User Guide-Second Edition
- Effects of the Checkpoint Interval on Time and Space in Time Warp
- Transputer System User Guide
- YADDES-Yet Another Distributed Discrete Event Simulator: User Manual
- Prediction and Lookahead in Distributed Simulation
- The Yaddes Distributed Discrete Event Simulation Specification Language and Execution Environments
- A Unified Modeling Methodology for Performance Evaluation of Distributed Discrete Event Simulation Mechanisms
- Semi-static Dataflow
- A Cache-based Message Passing Scheme for a Shared-bus Multiprocessor
- Theses
- Data Structures and Algorithms with Object-Oriented Design Patterns in Java
- Data Flow on a Queue Machine
- Design and Simulation of a Data-Flow Multiprocessor
- LARNS: A Powerful Model and Software Package for the Simulation of Local Area Ring Networks
- Unpublished Manuscripts
- A Template-based Model for Developing Parallel Applications on a Network Cluster
- A Pattern-Based Model for Developing Parallel Applications Using a Network of Processors
- A Skeleton-Based Model for Developing Parallel Applications Using a Network of Processors
- An Attributed, Time-Delayed Rendezvous Model for Parallel Discrete Event Simulation
- Dynamic Rescheduling of Tasks for the Macro-Dataflow Paradigm
- Ynot Logic Simulator: A Literate C Program
- Solutions Manual: Data Structures and Algorithms with Object-Oriented Design Patterns in Java
- A Time-Delayed-Rendezvous Model for Parallel Discrete Event Simulation
- A New Model for Parallel Discrete Event Simulation
- Parallel Simulation and Lotos: Research In Progress
- Hobbes: A Multi-Threaded Superscalar Architecture
- Dynamic Checkpoint Interval Selection in Time Warp Simulation
- Yaddes-Yet Another Distributed Discrete Event Simulator
- Queue Machines
- Effective Memory Bandwidth of Band-Connected Partial Crossbars
- An Occam Compiler for a Dataflow Multiprocessor (Extended Abstract)
- Presentations
- Solutions Manual: Data Structures and Algorithms with Object-Oriented Design Patterns in C
- Opuses (Opera?)
- Personal
- Home Address
- CV and Resume
- References
- Data Structures and Algorithms with Object-Oriented Design Patterns in C
- Personal
- Research
- Bruno R. Preiss-Signature Page
- Bruno s Home Page
- 404 Not Found
- 404 Not Found
- Copyright Notice
- Data Structures and Algorithms with Object-Oriented Design Patterns in C
- Bruno R. Preiss-Signature Page
- Data Structures and Algorithms with Object-Oriented Design Patterns in C
- Footnotes
- Colophon
- Introduction
- Multi-Dimensional Arrays
- Array Subscript Calculations
- Two-Dimensional Array Implementation
- Multi-Dimensional Subscripting in C
- Canonical Matrix Multiplication
- Exercises
- Projects
- Data Types and Abstraction
- Abstract Data Types
- Design Patterns
- What This Book Is About
- Class Hierarchy
- Objects
- Implementation
- The NullObject Singleton Class
- Implementation
- Object Wrappers for the Built-In Types
- Implementation
- Containers
- Visitors
- The IsDone Member Function
- Object-Oriented Design
- Container Class Default Put Member Function
- Iterators
- The NullIterator Class
- Direct vs. Indirect Containment
- Ownership of Contained Objects
- Associations
- Implementation
- Searchable Containers
- Exercises
- Projects
- Abstraction
- Stacks, Queues and Deques
- Stacks
- Array Implementation
- Member Variables
- Constructor and Destructor
- Push, Pop, and Top Member Functions
- The Accept Member Function
- Iterator
- Linked List Implementation
- Member Variables
- Encapsulation
- Constructor and Destructor
- Push, Pop, and Top Member Functions
- The Accept Member Function
- Iterator
- Applications
- Evaluating Postfix Expressions
- Implementation
- Queues
- Array Implementation
- Member Variables
- Object Hierarchies and Design Patterns
- Constructor and Destructor
- Head, Enqueue, and Dequeue Member Functions
- Linked List Implementation
- Member Variables
- Constructor and Destructor
- Head, Enqueue and Dequeue Member Functions
- Applications
- Implementation
- Deques
- Array Implementation
- Containers
- Tail, EnqueueHead, and DequeueTail Member Functions
- Linked List Implementation
- Tail, EnqueueHead, and DequeueTail Member Functions
- Doubly-Linked and Circular Lists
- Exercises
- Projects
- Ordered Lists and Sorted Lists
- Ordered Lists
- Array Implementation
- Member Variables
- Iterators
- Inserting and Accessing Items in a List
- Finding Items in a List
- Removing Items from a List
- Positions of Items in a List
- Finding the Position of an Item and Accessing by Position
- Inserting an Item at an Arbitrary Position
- Removing Arbitrary Items by Position
- Linked List Implementation
- Member Variables
- Inserting and Accessing Items in a List
- Visitors
- Finding Items in a List
- Removing Items from a List
- Positions of Items in a List
- Finding the Position of an Item and Accessing by Position
- Inserting an Item at an Arbitrary Position
- Removing Arbitrary Items by Position
- Performance Comparison: ListAsArray vs. ListAsLinkedList
- Applications
- Sorted Lists
- Array Implementation
- Adapters
- Inserting Items in a Sorted List
- Locating Items in an Array-Binary Search
- Finding Items in a Sorted List
- Removing Items from a List
- Linked List Implementation
- Inserting Items in a Sorted List
- Other Operations on Sorted Lists
- Performance Comparison: SortedListAsArray vs. SortedListAsList
- Applications
- Implementation
- Dedication
- Singletons
- Analysis
- Exercises
- Projects
- Hashing, Hash Tables and Scatter Tables
- Hashing-The Basic Idea
- Example
- Keys and Hash Functions
- Avoiding Collisions
- Spreading Keys Evenly
- Ease of Computation
- The Features of C You Need to Know
- Hashing Methods
- Division Method
- Middle Square Method
- Multiplication Method
- Fibonacci Hashing
- Hash Function Implementations
- Integral Keys
- Floating-Point Keys
- Character String Keys
- Hashing Objects
- Variables
- Hashing Containers
- Using Associations
- Hash Tables
- Separate Chaining
- Implementation
- Constructor and Destructor
- Inserting and Removing Items
- Finding an Item
- Average Case Analysis
- Scatter Tables
- Parameter Passing
- Chained Scatter Table
- Implementation
- Constructors and Destructor
- Inserting and Finding an Item
- Removing Items
- Worst-Case Running Time
- Average Case Analysis
- Scatter Table using Open Addressing
- Linear Probing
- Quadratic Probing
- Pointers
- Double Hashing
- Implementation
- Constructors and Destructor
- Inserting Items
- Finding Items
- Removing Items
- Average Case Analysis
- Applications
- Exercises
- Projects
- Classes and Objects
- Trees
- Basics
- Terminology
- More Terminology
- Alternate Representations for Trees
- N-ary Trees
- Binary Trees
- Tree Traversals
- Preorder Traversal
- Postorder Traversal
- Inheritance
- Inorder Traversal
- Breadth-First Traversal
- Expression Trees
- Infix Notation
- Prefix Notation
- Postfix Notation
- Implementing Trees
- Tree Traversals
- Depth-First Traversal
- Preorder, Inorder and Postorder Traversals
- Other Features
- Breadth-First Traversal
- Accept Member Function
- Tree Iterators
- Member Variables
- Constructor and Reset Member Function
- Operator Member Functions
- General Trees
- Member Variables
- Member Functions
- Constructor, Destructor, and Purge Member Function
- How This Book Is Organized
- Key and Subtree Member Functions
- AttachSubtree and DetachSubtree Member Functions
- N-ary Trees
- Member Variables
- Member Functions
- Constructors
- IsEmpty Member Function
- Key, AttachKey and DetachKey Member Functions
- Subtree, AttachSubtree and DetachSubtree Member Functions
- Binary Trees
- Models and Asymptotic Analysis
- Member Variables
- Constructors
- Destructor and Purge Member Functions
- Binary Tree Traversals
- Comparing Trees
- Applications
- Implementation
- Exercises
- Projects
- Search Trees
- Preface
- Foundational Data Structures
- Basics
- M-Way Search Trees
- Binary Search Trees
- Searching a Search Tree
- Searching an M-way Tree
- Searching a Binary Tree
- Average Case Analysis
- Successful Search
- Solving The Recurrence-Telescoping
- Unsuccessful Search
- Abstract Data Types and the Class Hierarchy
- Traversing a Search Tree
- Implementing Search Trees
- Binary Search Trees
- Member Variables
- Find Member Function
- FindMin Member Function
- Inserting Items in a Binary Search Tree
- Insert and AttachKey Member Functions
- Removing Items from a Binary Search Tree
- Withdraw and DetachKey Member Functions
- Data Structures
- AVL Search Trees
- Implementing AVL Trees
- Constructor
- Height, AdjustHeight and BalanceFactor Member Functions
- Inserting Items into an AVL Tree
- Balancing AVL Trees
- Single Rotations
- Double Rotations
- Implementation
- Removing Items from an AVL Tree
- Algorithms
- M-Way Search Trees
- Implementing M-Way Search Trees
- Implementation
- Member Functions
- Inorder Traversal
- Finding Items in an M-Way Search Tree
- Linear Search
- Binary Search
- Inserting Items into an M-Way Search Tree
- Removing Items from an M-Way Search Tree
- Algorithm Analysis
- B-Trees
- Implementing B-Trees
- Member Variables
- Constructors
- Private Member Functions
- Inserting Items into a B-Tree
- Implementation
- Running Time Analysis
- Removing Items from a B-Tree
- Applications
- A Detailed Model of the Computer
- Exercises
- Projects
- Heaps and Priority Queues
- Basics
- Binary Heaps
- Complete Trees
- Complete N-ary Trees
- Implementation
- Member Variables
- Constructor, Destructor and Purge Member Functions
- The Basic Axioms
- Putting Items into a Binary Heap
- Removing Items from a Binary Heap
- Leftist Heaps
- Leftist Trees
- Implementation
- Member Variables
- SwapContents Member Function
- Merging Leftist Heaps
- Putting Items into a Leftist Heap
- Removing Items from a Leftist Heap
- A Simple Example-Arithmetic Series Summation
- Binomial Queues
- Binomial Trees
- Binomial Queues
- Implementation
- Heap-Ordered Binomial Trees
- Binomial Queues
- Member Variables
- AddTree and RemoveTree
- FindMinTree and FindMin Member Functions
- Merging Binomial Queues
- Array Subscripting Operations
- Putting Items into a Binomial Queue
- Removing an Item from a Binomial Queue
- Applications
- Discrete Event Simulation
- Implementation
- Exercises
- Projects
- Sets, Multisets and Partitions
- Basics
- Implementing Sets
- Another Example-Horner s Rule
- Array and Bit-Vector Sets
- Basic Operations
- Union, Intersection and Difference
- Comparing Sets
- Bit-Vector Sets
- Basic Operations
- Union, Intersection and Difference
- Multisets
- Array Implementation
- Basic Operations
- Goals
- Analyzing Recursive Functions
- Union, Intersection and Difference
- Linked List Implementation
- Union
- Intersection
- Partitions
- Representing Partitions
- Implementing a Partition using a Forest
- Implementation
- Constructors and Destructor
- Find and Join Member Functions
- Solving Recurrence Relations-Repeated Substitution
- Collapsing Find
- Union by Size
- Union by Height or Rank
- Applications
- Exercises
- Projects
- Dynamic Storage Allocation: The Other Kind of Heap
- Basics
- C Magic
- Working with Multiple Storage Pools
- Yet Another Example-Finding the Largest Element of an Array
- The Heap
- Singly Linked Free Storage
- Implementation
- Constructor and Destructor
- Acquiring an Area
- Releasing an Area
- Doubly Linked Free Storage
- Implementation
- Constructor and Destructor
- Releasing an Area
- Average Running Times
- Acquiring an Area
- Buddy System for Storage Management
- Implementation
- Constructor and Destructor
- Acquiring an Area
- Releasing an Area
- Applications
- Implementation
- Exercises
- Projects
- About Harmonic Numbers
- Algorithmic Patterns and Problem Solvers
- Brute-Force and Greedy Algorithms
- Example-Counting Change
- Brute-Force Algorithm
- Greedy Algorithm
- Example-01 Knapsack Problem
- Backtracking Algorithms
- Example-Balancing Scales
- Representing the Solution Space
- Abstract Backtracking Solvers
- Best-Case and Worst-Case Running Times
- Depth-First Solver
- Breadth-First Solver
- Branch-and-Bound Solvers
- Depth-First, Branch-and-Bound Solver
- Example-01 Knapsack Problem Again
- Top-Down Algorithms: Divide-and-Conquer
- Example-Binary Search
- Example-Computing Fibonacci Numbers
- Example-Merge Sorting
- Running Time of Divide-and-Conquer Algorithms
- The Last Axiom
- Case 1 (tex2html_wrap_inline68825)
- Case 2 (tex2html_wrap_inline68839)
- Case 3 (tex2html_wrap_inline68849)
- Summary
- Example-Matrix Multiplication
- Bottom-Up Algorithms: Dynamic Programming
- Example-Generalized Fibonacci Numbers
- Example-Computing Binomial Coefficients
- Application: Typesetting Problem
- Example
- A Simplified Model of the Computer
- Implementation
- Randomized Algorithms
- Generating Random Numbers
- The Minimal Standard Random Number Generator
- Implementation
- Random Variables
- Implementation
- Monte Carlo Methods
- Example-Computing tex2html_wrap_inline69477
- Simulated Annealing
- An Example-Geometric Series Summation
- Example-Balancing Scales
- Exercises
- Projects
- Sorting Algorithms and Sorters
- Basics
- Sorting and Sorters
- Sorter Class Hierarchy
- Insertion Sorting
- Straight Insertion Sort
- Implementation
- About Arithmetic Series Summation
- Average Running Time
- Binary Insertion Sort
- Exchange Sorting
- Bubble Sort
- Quicksort
- Implementation
- Running Time Analysis
- Worst-Case Running Time
- Best-Case Running Time
- Average Running Time
- Approach
- Example-Geometric Series Summation Again
- Selecting the Pivot
- Selection Sorting
- Straight Selection Sorting
- Implementation
- Sorting with a Heap
- Implementation
- Building the Heap
- Running Time Analysis
- The Sorting Phase
- Merge Sorting
- About Geometric Series Summation
- Implementation
- Merging
- Two-Way Merge Sorting
- Running Time Analysis
- A Lower Bound on Sorting
- Distribution Sorting
- Bucket Sort
- Implementation
- Radix Sort
- Implementation
- Example-Computing Powers
- Performance Data
- Exercises
- Projects
- Graphs and Graph Algorithms
- Basics
- Directed Graphs
- Terminology
- More Terminology
- Directed Acyclic Graphs
- Undirected Graphs
- Example-Geometric Series Summation Yet Again
- Terminology
- Labeled Graphs
- Representing Graphs
- Adjacency Matrices
- Sparse vs. Dense Graphs
- Adjacency Lists
- Implementing Graphs
- Implementing Vertices
- Implementing Edges
- Abstract Graphs and Digraphs
- Exercises
- Accessors and Mutators
- Iterators
- Graph Traversals
- Implementing Undirected Graphs
- Using Adjacency Matrices
- Using Adjacency Lists
- Edge-Weighted and Vertex-Weighted Graphs
- Comparison of Graph Representations
- Space Comparison
- Time Comparison
- Projects
- Graph Traversals
- Depth-First Traversal
- Implementation
- Running Time Analysis
- Breadth-First Traversal
- Implementation
- Running Time Analysis
- Topological Sort
- Implementation
- Running Time Analysis
- Asymptotic Notation
- Graph Traversal Applications: Testing for Cycles and Connectedness
- Connectedness of an Undirected Graph
- Connectedness of a Directed Graph
- Testing for Cycles in a Directed Graph
- Shortest-Path Algorithms
- Single-Source Shortest Path
- Dijkstra s Algorithm
- Data Structures for Dijkstra s Algorithm
- Implementation
- Running Time Analysis
- An Asymptotic Upper Bound-Big Oh
- All-Pairs Source Shortest Path
- Floyd s Algorithm
- Implementation
- Running Time Analysis
- Minimum-Cost Spanning Trees
- Constructing Spanning Trees
- Minimum-Cost Spanning Trees
- Prim s Algorithm
- Implementation
- Kruskal s Algorithm
- A Simple Example
- Implementation
- Running Time Analysis
- Application: Critical Path Analysis
- Implementation
- Exercises
- Projects
- C and Object-Oriented Programming
- Variables, Pointers and References
- Pointers Are Variables
- Dereferencing Pointers
- Big Oh Fallacies and Pitfalls
- References are Not Variables
- Parameter Passing
- Pass By Value
- Pass By Reference
- The Trade-off
- Constant Parameters
- Objects and Classes
- Member Variables and Member Functions
- Constructors and Destructors
- Default Constructor
- Outline
- Properties of Big Oh
- Copy Constructor
- The Copy Constructor, Parameter Passing and Function Return Values
- Destructors
- Accessors and Mutators
- Mutators
- Member Access Control
- Inheritance and Polymorphism
- Derivation and Inheritance
- Derivation and Access Control
- Polymorphism
- About Polynomials
- Virtual Member Functions
- Abstract Classes and Concrete Classes
- Algorithmic Abstraction
- Multiple Inheritance
- Run-Time Type Information and Casts
- Templates
- Exceptions
- Class Hierarchy Diagrams
- Character Codes
- References
- About Logarithms
- Index
- Tight Big Oh Bounds
- More Big Oh Fallacies and Pitfalls
- Conventions for Writing Big Oh Expressions
- An Asymptotic Lower Bound-Omega
- A Simple Example
- About Polynomials Again
- More Notation-Theta and Little Oh
- Suggested Course Outline
- Asymptotic Analysis of Algorithms
- Rules For Big Oh Analysis of Running Time
- Example-Prefix Sums
- Example-Fibonacci Numbers
- Example-Bucket Sort
- Reality Check
- Checking Your Analysis
- Exercises
- Projects
- Foundational Data Structures
- Online Course Materials
- Dynamic Arrays
- Default Constructor
- Array Constructor
- Copy Constructor
- Destructor
- Array Member Functions
- Array Subscripting Operator
- Resizing an Array
- Singly-Linked Lists
- An Implementation
- Contents
- List Elements
- Default Constructor
- Destructor and Purge Member Function
- Accessors
- First and Last Functions
- Prepend
- Append
- Copy Constructor and Assignment Operator
- Extract
- InsertAfter and InsertBefore
- 404 Not Found
- Bruno Richard Preiss: Curriculum Vita
- Degrees
- Patents
- Books
- Conference Papers (full paper refereed)
- Conference Papers (abstract refereed)
- Submitted Conference Papers
- Technical Reports
- Theses
- Presentations, Seminars, Invited Talks
- Research Grants
- Teaching Record
- Diplomas
- Supervision of Students
- Graduate Students
- NSERC Undergraduate Summer Research AssistantsCo-op Students
- UW Undergraduate Research Assistants
- ECE499 Projects
- Graduate Student Theses Supervised
- Service to the University of Waterloo
- Service to the Profession
- Scholarships and Awards
- Employment record
- Membership in Professional Organizations and Societies
- Publications
- Refereed Full Journal Papers
- Submitted Journal Papers
- Refereed Technical Notes
- resume
Data Structures and Algorithms with Object-Oriented Design Patterns in C++
ISBN: 0471241342
EAN: 2147483647
EAN: 2147483647
Year: 1998
Pages: 101
Pages: 101
Authors: Bruno R. Preiss