## Data Structures and Algorithms in JavaUsing a unique multimedia format for learning the fundamentals of data structures and algorithms, this conceptually elegant and innovative text incorporates the object-oriented design paradigm with Java as the implementation language. The result is a learning experience that provides the fundamental intuition and analysis of each structure studied. A Web site complete with Java applications and applets accompanies the text. Includes CD-ROM with... The Microsoft Visual J++ programming environment. |

### From inside the book

Results 1-3 of 89

Page 175

public interface Operatorlnfo { // Generic operator stored at an internal node of an

expression tree public

AdditionOperator implements Operatorlnfo { public

{ return new String("+"); } } public class MultiplicationOperator implements

Operatorlnfo { public

intValue() * y.

public interface Operatorlnfo { // Generic operator stored at an internal node of an

expression tree public

**Integer**operation(lnteger x,**Integer**y); } public classAdditionOperator implements Operatorlnfo { public

**Integer**operation(lnteger x,**Integer**y) { return new lnteger(x.intValue() + y.intValueQ); I public String toString(){ return new String("+"); } } public class MultiplicationOperator implements

Operatorlnfo { public

**Integer**operation(lnteger x,**Integer**y) { return new lnteger(x.intValue() * y.

Page 289

Justification: Let Z denote the set of

separate each hash function h0fb into the functions fa,b(k) = ak + b mod p and g(k

) = k mod N so that ha,b(k) = g(fa,b(k)). The set of functions faj, defines a family of

hash functions F that map

function in F causes no collisions at all. To justify this claim, consider fa,b{j) an^ fa

,b(k) for some pair of different

would have a ...

Justification: Let Z denote the set of

**integers**in the range [0,p— 1]. Let usseparate each hash function h0fb into the functions fa,b(k) = ak + b mod p and g(k

) = k mod N so that ha,b(k) = g(fa,b(k)). The set of functions faj, defines a family of

hash functions F that map

**integers**in Z to**integers**in Z. We claim that eachfunction in F causes no collisions at all. To justify this claim, consider fa,b{j) an^ fa

,b(k) for some pair of different

**integers**j and k in Z. If fa,b(j) — fa,b(k), then wewould have a ...

Page 339

C-8.10 Suppose we are given a sequence S of n elements, each of which is an

time. (Hint: think of alternate ways of viewing the elements.) C-8.11 Let 5i,52,...,5*

be k different sequences, whose elements have

1], for some parameter N > 2. Describe an algorithm running in 0(k + n-\-N) time

for sorting all the sequences, where n denotes the total size of all the sequences.

C-8.10 Suppose we are given a sequence S of n elements, each of which is an

**integer**in the range [0,«2 — 1]. Describe a simple method for sorting S in 0(n)time. (Hint: think of alternate ways of viewing the elements.) C-8.11 Let 5i,52,...,5*

be k different sequences, whose elements have

**integer**keys in the range [0,/V —1], for some parameter N > 2. Describe an algorithm running in 0(k + n-\-N) time

for sorting all the sequences, where n denotes the total size of all the sequences.

### What people are saying - Write a review

#### LibraryThing Review

User Review - daschaich - LibraryThingThird edition is much improved: When I learned that this was the required book for my introductory data structures class this semester, I was somewhat worried by the large number of very negative ... Read full review

### Contents

Analysis Tools | 30 |

Stacks Queues and Linked Lists | 66 |

Sequences | 114 |

Copyright | |

19 other sections not shown

### Other editions - View all

Data Structures and Algorithms in Java Michael T. Goodrich,Roberto Tamassia No preview available - 2010 |

Data Structures and Algorithms in Java Michael T. Goodrich,Roberto Tamassia No preview available - 2004 |

### Common terms and phrases

abstract data type analysis applet array asymptotic AVL tree binary search tree binary tree block boolean called chapter Code Fragment constant constructor container data structure defined deletion denote deque describe dictionary doubly linked list edges efficient empty enumeration Euler tour example executed external Figure function given hash heap height Input insertion instance variables integer interface internal node isEmpty iteration Java implementation Java Virtual Machine justification list structure loop memory merge-sort method methpo number of elements object-oriented design Output path perform position postorder traversal preorder traversal primitive operations priority queue problem Proposition protected void pseudo-code public class public void query queue ADT quick-sort random recursive red-black tree reference remove running Section sequence ADT shown in Code singly linked list skip list specific splay splay tree stack string structures and algorithms subtree rooted update vertex vertices worst-case