Data Structures And Algorithm Analysis in C 4th Edition by Mark Weiss 013284737X 9780132847377

Data Structures And Algorithm Analysis in C 4th Edition by Mark Weiss – Ebook PDF Instant Download/Delivery. 013284737X, 9780132847377

Full download Data Structures And Algorithm Analysis in C 4th Edition after payment

Product details:

ISBN 10: 013284737X

ISBN 13: 9780132847377

Author: Mark A. Weiss

This is the eBook of the printed book and may not include any media, website access codes, or print supplements that may come packaged with the bound book. Data Structures and Algorithm Analysis in C++ is an advanced algorithms book that bridges the gap between traditional CS2 and Algorithms Analysis courses. As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs using the C++ programming language. This book explains topics from binary heaps to sorting to NP-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weiss’ careful, rigorous and in-depth analysis of each type of algorithm.

Data Structures And Algorithm Analysis in C 4th Table of contents:

Chapter 1 Programming: A General Overview

1.1 What’s This Book About?

1.2 Mathematics Review

1.2.1 Exponents

1.2.2 Logarithms

Definition 1.1

Theorem 1.1

Proof

Theorem 1.2

Proof

1.2.3 Series

1.2.4 Modular Arithmetic

1.2.5 The P Word

Proof by Induction

Theorem 1.3

Proof

Proof by Counterexample

Proof by Contradiction

1.3 A Brief Introduction to Recursion

Printing Out Numbers

Recursion and Induction

Theorem 1.4

Proof (By induction on the number of digits in n)

1.4 C++ Classes

1.4.1 Basic class Syntax

1.4.2 Extra Constructor Syntax and Accessors

Default Parameters

Initialization List

explicit Constructor

Constant Member Function

1.4.3 Separation of Interface and Implementation

Preprocessor Commands

Scope Resolution Operator

Signatures Must Match Exactly

Objects Are Declared Like Primitive Types

1.4.4 vector and string

1.5 C++ Details

1.5.1 Pointers

Declaration

Dynamic Object Creation

Garbage Collection and delete

Assignment and Comparison of Pointers

Accessing Members of an Object through a Pointer

Address-of Operator (&)

1.5.2 Lvalues, Rvalues, and References

lvalue references use #1: aliasing complicated names

lvalue references use #2: range for loops

lvalue references use #3: avoiding a copy

1.5.3 Parameter Passing

1.5.4 Return Passing

1.5.5 std::swap and std::move

1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator=

Destructor

Copy Constructor and Move Constructor

Copy Assignment and Move Assignment (operator=)

Defaults

When the Defaults Do Not Work

1.5.7 C-style Arrays and Strings

1.6 Templates

1.6.1 Function Templates

1.6.2 Class Templates

1.6.3 Object, Comparable, and an Example

1.6.4 Function Objects

1.6.5 Separate Compilation of Class Templates

1.7 Using Matrices

1.7.1 The Data Members, Constructor, and Basic Accessors

1.7.2 operator[]

1.7.3 Big-Five

Summary

Exercises

References

Chapter 2 Algorithm Analysis

2.1 Mathematical Background

Definition 2.1

Definition 2.2

Definition 2.3

Definition 2.4

2.2 Model

2.3 What to Analyze

2.4 Running-Time Calculations

2.4.1 A Simple Example

2.4.2 General Rules

2.4.3 Solutions for the Maximum Subsequence Sum Problem

2.4.4 Logarithms in the Running Time

Binary Search

Euclid’s Algorithm

Theorem 2.1

Proof

Exponentiation

2.4.5 Limitations of Worst-Case Analysis

Summary

Exercises

References

Chapter 3 Lists, Stacks, and Queues

3.1 Abstract Data Types (ADTs)

3.2 The List ADT

3.2.1 Simple Array Implementation of Lists

3.2.2 Simple Linked Lists

3.3 vector and list in the STL

3.3.1 Iterators

Getting an Iterator

Iterator Methods

Container Operations That Require Iterators

3.3.2 Example: Using erase on a List

3.3.3 const_iterators

3.4 Implementation of vector

3.5 Implementation of list

3.6 The Stack ADT

3.6.1 Stack Model

3.6.2 Implementation of Stacks

Linked List Implementation of Stacks

Array Implementation of Stacks

3.6.3 Applications

Balancing Symbols

Postfix Expressions

Infix to Postfix Conversion

Function Calls

3.7 The Queue ADT

3.7.1 Queue Model

3.7.2 Array Implementation of Queues

3.7.3 Applications of Queues

Summary

Exercises

Chapter 4 Trees

4.1 Preliminaries

4.1.1 Implementation of Trees

4.1.2 Tree Traversals with an Application

4.2 Binary Trees

4.2.1 Implementation

4.2.2 An Example: Expression Trees

Constructing an Expression Tree

4.3 The Search Tree ADT—Binary Search Trees

4.3.1 contains

4.3.2 findMin and findMax

4.3.3 insert

4.3.4 remove

4.3.5 Destructor and Copy Constructor

4.3.6 Average-Case Analysis

4.4 AVL Trees

4.4.1 Single Rotation

4.4.2 Double Rotation

4.5 Splay Trees

4.5.1 A Simple Idea (That Does Not Work)

4.5.2 Splaying

4.6 Tree Traversals (Revisited)

4.7 B-Trees

4.8 Sets and Maps in the Standard Library

4.8.1 Sets

4.8.2 Maps

4.8.3 Implementation of set and map

4.8.4 An Example That Uses Several Maps

Summary

Exercises

References

Chapter 5 Hashing

5.1 General Idea

5.2 Hash Function

5.3 Separate Chaining

5.4 Hash Tables without Linked Lists

5.4.1 Linear Probing

5.4.2 Quadratic Probing

Theorem 5.1

Proof

5.4.3 Double Hashing

5.5 Rehashing

5.6 Hash Tables in the Standard Library

5.7 Hash Tables with Worst-Case O(1) Access

5.7.1 Perfect Hashing

Theorem 5.2

Proof

Theorem 5.3

Proof

5.7.2 Cuckoo Hashing

Cuckoo Hash Table Implementation

5.7.3 Hopscotch Hashing

5.8 Universal Hashing

Definition 5.1

Definition 5.2

Theorem 5.4

Proof

5.9 Extendible Hashing

Summary

Exercises

References

Chapter 6 Priority Queues (Heaps)

6.1 Model

6.2 Simple Implementations

6.3 Binary Heap

6.3.1 Structure Property

6.3.2 Heap-Order Property

6.3.3 Basic Heap Operations

insert

deleteMin

6.3.4 Other Heap Operations

decreaseKey

increaseKey

remove

buildHeap

Theorem 6.1

Proof

6.4 Applications of Priority Queues

6.4.1 The Selection Problem

Algorithm 6A

Algorithm 6B

6.4.2 Event Simulation

6.5 d-Heaps

6.6 Leftist Heaps

6.6.1 Leftist Heap Property

Theorem 6.2

Proof

6.6.2 Leftist Heap Operations

6.7 Skew Heaps

6.8 Binomial Queues

6.8.1 Binomial Queue Structure

6.8.2 Binomial Queue Operations

6.8.3 Implementation of Binomial Queues

6.9 Priority Queues in the Standard Library

Summary

Exercises

References

Chapter 7 Sorting

7.1 Preliminaries

7.2 Insertion Sort

7.2.1 The Algorithm

7.2.2 STL Implementation of Insertion Sort

7.2.3 Analysis of Insertion Sort

7.3 A Lower Bound for Simple Sorting Algorithms

Theorem 7.1

Proof

Theorem 7.2

Proof

7.4 Shellsort

7.4.1 Worst-Case Analysis of Shellsort

Theorem 7.3

Proof

Theorem 7.4

Proof

7.5 Heapsort

7.5.1 Analysis of Heapsort

Theorem 7.5

Proof

7.6 Mergesort

7.6.1 Analysis of Mergesort

7.7 Quicksort

7.7.1 Picking the Pivot

A Wrong Way

A Safe Maneuver

Median-of-Three Partitioning

7.7.2 Partitioning Strategy

7.7.3 Small Arrays

7.7.4 Actual Quicksort Routines

7.7.5 Analysis of Quicksort

Worst-Case Analysis

Best-Case Analysis

Average-Case Analysis

7.7.6 A Linear-Expected-Time Algorithm for Selection

7.8 A General Lower Bound for Sorting

7.8.1 Decision Trees

Proof

Proof

Theorem 7.6

Proof

Theorem 7.7

Proof

7.9 Decision-Tree Lower Bounds for Selection Problems

Proof

Theorem 7.8

Proof

Proof

Proof

Theorem 7.9

Proof

Theorem 7.10

Proof

Theorem 7.11

Proof

7.10 Adversary Lower Bounds

Theorem 7.8 (restated)

Lower Bound for Finding the Minimum and Maximum

Theorem 7.12

Proof

7.11 Linear-Time Sorts: Bucket Sort and Radix Sort

7.12 External Sorting

7.12.1 Why We Need New Algorithms

7.12.2 Model for External Sorting

7.12.3 The Simple Algorithm

7.12.4 Multiway Merge

7.12.5 Polyphase Merge

7.12.6 Replacement Selection

Summary

Exercises

References

Chapter 8 The Disjoint Sets Class

8.1 Equivalence Relations

8.2 The Dynamic Equivalence Problem

8.3 Basic Data Structure

8.4 Smart Union Algorithms

8.5 Path Compression

8.6 Worst Case for Union-by-Rank and Path Compression

8.6.1 Slowly Growing Functions

8.6.2 An Analysis by Recursive Decomposition

Proof

Proof

Partial Path Compression

A Recursive Decomposition

Proof

Proof

Proof

Theorem 8.1

Proof

Theorem 8.2

Proof

8.6.3 An O( M log*N) Bound

Theorem 8.3

Proof

8.6.4 An O( M α(M,N)) Bound

Theorem 8.4

Proof

Theorem 8.5

Proof

Theorem 8.6

Proof

8.7 An Application

Summary

Exercises

References

Chapter 9 Graph Algorithms

9.1 Definitions

9.1.1 Representation of Graphs

9.2 Topological Sort

9.3 Shortest-Path Algorithms

9.3.1 Unweighted Shortest Paths

9.3.2 Dijkstra’s Algorithm

9.3.3 Graphs with Negative Edge Costs

9.3.4 Acyclic Graphs

9.3.5 All-Pairs Shortest Path

9.3.6 Shortest Path Example

9.4 Network Flow Problems

9.4.1 A Simple Maximum-Flow Algorithm

9.5 Minimum Spanning Tree

9.5.1 Prim’s Algorithm

9.5.2 Kruskal’s Algorithm

9.6 Applications of Depth-First Search

9.6.1 Undirected Graphs

9.6.2 Biconnectivity

9.6.3 Euler Circuits

9.6.4 Directed Graphs

9.6.5 Finding Strong Components

9.7 Introduction to NP-Completeness

9.7.1 Easy vs. Hard

9.7.2 The Class NP

9.7.3 NP-Complete Problems

Summary

Exercises

References

Chapter 10 Algorithm Design Techniques

10.1 Greedy Algorithms

10.1.1 A Simple Scheduling Problem

Multiprocessor Case

Minimizing the Final Completion Time

10.1.2 Huffman Codes

Huffman’s Algorithm

10.1.3 Approximate Bin Packing

Online Algorithms

Theorem 10.1

Proof

Next Fit

Theorem 10.2

Proof

First Fit

Theorem 10.3

Proof

Best Fit

Offline Algorithms

Proof

Proof

Theorem 10.4

Proof

Theorem 10.5

Proof

10.2 Divide and Conquer

10.2.1 Running Time of Divide-and-Conquer Algorithms

Theorem 10.6

Proof

Theorem 10.7

Theorem 10.8

10.2.2 Closest-Points Problem

10.2.3 The Selection Problem

Theorem 10.9

Proof

Reducing the Average Number of Comparisons

10.2.4 Theoretical Improvements for Arithmetic Problems

Multiplying Integers

Matrix Multiplication

10.3 Dynamic Programming

10.3.1 Using a Table Instead of Recursion

10.3.2 Ordering Matrix Multiplications

10.3.3 Optimal Binary Search Tree

10.3.4 All-Pairs Shortest Path

10.4 Randomized Algorithms

10.4.1 Random-Number Generators

10.4.2 Skip Lists

10.4.3 Primality Testing

Theorem 10.10 (Fermat’s Lesser Theorem)

Proof

Theorem 10.11

Proof

10.5 Backtracking Algorithms

10.5.1 The Turnpike Reconstruction Problem

10.5.2 Games

Minimax Strategy

α–β Pruning

Summary

Exercises

References

Chapter 11 Amortized Analysis

11.1 An Unrelated Puzzle

11.2 Binomial Queues

Theorem 11.1

Proof

11.3 Skew Heaps

Definition

Theorem 11.2

Proof

11.4 Fibonacci Heaps

11.4.1 Cutting Nodes in Leftist Heaps

11.4.2 Lazy Merging for Binomial Queues

Amortized Analysis of Lazy Binomial Queues

Theorem 11.3

Proof

11.4.3 The Fibonacci Heap Operations

11.4.4 Proof of the Time Bound

Proof

Proof

Proof

Theorem 11.4

Proof

11.5 Splay Trees

Proof

Theorem 11.5

Proof

Summary

Exercises

References

Chapter 12 Advanced Data Structures and Implementation

12.1 Top-Down Splay Trees

12.2 Red-Black Trees

12.2.1 Bottom-Up Insertion

12.2.2 Top-Down Red-Black Trees

12.2.3 Top-Down Deletion

12.3 Treaps

12.4 Suffix Arrays and Suffix Trees

12.4.1 Suffix Arrays

12.4.2 Suffix Trees

12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees

12.5 k-d Trees

12.6 Pairing Heaps

People also search for Data Structures And Algorithm Analysis in C 4th: 

data structures and algorithm analysis in c ++ 4th edition

data structure and algorithm analysis

why we need to do algorithm analysis in data structure

 what is the importance of data structures and algorithms