Algorithms and Data Structures in C++:Table of Contents

Algorithms and Data Structures in C++
by Alan Parker
CRC Press, CRC Press LLC
ISBN: 0849371716 Pub Date: 08/01/93

Preface

Chapter 1—Data Representations

1.1 Integer Representations

1.1.1 Unsigned Notation
1.1.2 Signed-Magnitude Notation
1.1.3 2’s Complement Notation
1.1.4 Sign Extension

1.1.4.1 Signed-Magnitude
1.1.4.2 Unsigned
1.1.4.3 2’s Complement

1.1.5 C++ Program Example

1.2 Floating Point Representation

1.2.1 IEEE 754 Standard Floating Point Representations

1.2.1.1 IEEE 32-Bit Standard
1.2.1.2 IEEE 64-bit Standard
1.2.1.3 C++ Example for IEEE Floating point

1.2.2 Bit Operators in C++
1.2.3 Examples
1.2.4 Conversion from Decimal to Binary

1.3 Character Formats—ASCII
1.4 Putting it All Together
1.5 Problems

Chapter 2—Algorithms

2.1 Order

2.1.1 Justification of Using Order as a Complexity Measure

2.2 Induction
2.3 Recursion

2.3.1 Factorial
2.3.2 Fibonacci Numbers
2.3.3 General Recurrence Relations
2.3.4 Tower of Hanoi
2.3.5 Boolean Function Implementation

2.4 Graphs and Trees
2.5 Parallel Algorithms

2.5.1 Speedup and Amdahls Law
2.5.2 Pipelining
2.5.3 Parallel Processing and Processor Topologies

2.5.3.1 Full Crossbar
2.5.3.2 Rectangular Mesh
2.5.3.3 Hypercube
2.5.3.4 Cube-Connected Cycles

2.6 The Hypercube Topology

2.6.1 Definitions
2.6.2 Message Passing
2.6.3 Efficient Hypercubes

2.6.3.1 Transitive Closure
2.6.3.2 Least-Weighted Path-Length
2.6.3.3 Hypercubes with Failed Nodes
2.6.3.4 Efficiency
2.6.3.5 Message Passing in Efficient Hypercubes

2.6.4 Visualizing the Hypercube: A C++ Example

2.7 Problems

Chapter 3—Data Structures and Searching

3.1 Pointers and Dynamic Memory Allocation

3.1.1 A Double Pointer Example
3.1.2 Dynamic Memory Allocation with New and Delete
3.1.3 Arrays
3.1.4 Overloading in C++

3.2 Arrays
3.3 Stacks
3.4 Linked Lists

3.4.1 Singly Linked Lists
3.4.2 Circular Lists
3.4.3 Doubly Linked Lists

3.5 Operations on Linked Lists

3.5.1 A Linked List Example

3.5.1.1 Bounding a Search Space

3.6 Linear Search
3.7 Binary Search
3.8 QuickSort
3.9 Binary Trees

3.9.1 Traversing the Tree

3.10 Hashing
3.11 Simulated Annealing

3.11.1 The Square Packing Problem

3.11.1.1 Program Description

3.12 Problems

Chapter 4—Algorithms for Computer Arithmetic

4.1 2’s Complement Addition

4.1.1 Full and Half Adder
4.1.2 Ripple Carry Addition

4.1.2.1 Overflow

4.1.3 Carry Lookahead Addition

4.2 A Simple Hardware Simulator in C++
4.3 2’s Complement Multiplication

4.3.1 Shift-Add Addition
4.3.2 Booth Algorithm
4.3.3 Bit-Pair Recoding

4.4 Fixed Point Division

4.4.1 Restoring Division
4.4.2 Nonrestoring Division
4.4.3 Shifting over 1’s and 0’s
4.4.4 Newton’s Method

4.5 Residue Number System

4.5.1 Representation in the Residue Number System
4.5.2 Data Conversion — Calculating the Value of a Number
4.5.3 C++ Implementation

4.6 Problems