Java Collections: An Introduction to Abstract Data Types, Data Structures and Algorithms / Edition 1

Paperback (Print)
Buy New
Buy New from BN.com
$78.48
Used and New from Other Sellers
Used and New from Other Sellers
from $1.99
Usually ships in 1-2 business days
(Save 97%)
Other sellers (Paperback)
  • All (11) from $1.99   
  • New (4) from $36.16   
  • Used (7) from $1.99   

Overview

A unique, practical approach to working with collection classes in Java 2
Software developers new to Java will find the practical, software-engineering based approach taken by this book extremely refreshing. With an emphasis more on software design and less on theory, Java Collections explores in detail Java 2 collection classes, helping programmers choose the best collection classes for each application they work on. Watt and Brown explore abstract data types (ADTs) that turn up again and again in software design, using them to provide context for the data structures required for their implementation and the algorithms associated with the data structures. Numerous worked examples, several large case studies, and end-of-chapter exercises are also provided.

Read More Show Less

Editorial Reviews

Booknews
This textbook for a second-level course in algorithms and data structures focuses on abstract data types (ADTs) that occur repeatedly in software design. Watt (University of Glasgow) and Brown (Robert Gordon University) use these ADTs to introduce and motivate the data structures required to implement them and the algorithms associated with the data structures. Annotation c. Book News, Inc., Portland, OR (booknews.com)
Read More Show Less

Product Details

  • ISBN-13: 9780471899785
  • Publisher: Wiley
  • Publication date: 3/28/2001
  • Edition description: New Edition
  • Edition number: 1
  • Pages: 566
  • Product dimensions: 7.46 (w) x 9.27 (h) x 1.21 (d)

Meet the Author

David Watt is a Professor of Computing Science at the University of Glasgow.
Deryck Brown is a Senior Lecturer in Computing Science at the Robert Gordon University, Aberdeen.

Read More Show Less

Read an Excerpt

Chapter 1: Algorithms

In this chapter we shall study:
  • fundamental principles of algorithms: problems that can or cannot be solved by algorithms, properties of algorithms themselves, and notation for algorithms (Section 2. I )
  • analysis of algorithms to determine their time and space efficiency (Section 2.2)
  • the notion of complexity of algorithms (Section 2.3)
  • recursive algorithms and their complexity (Section 2.4).
2.1 Principles of algorithms

In Section 1.1 we encountered a variety of algorithms. In this section we briefly discuss some fundamental issues concerned with problems, algorithms, and notation.

Problems

Concerning problems, we can state the following principles:

  • An algorithm must be designed to solve a stated problem, which is a well-defined task that has to be performed.
  • The problem must be solvable by an algorithm.
We have already (in Section 1.1) encountered a number of problems that can be solved by algorithms. We can also pose some problems that are not solvable by algorithms. To say that a problem is unsolvable does not just mean that an algorithm has not yet been found to solve it. It means that such an algorithm can never be found. A human might eventually solve the problem, but only by applying insight and creativity, not by following a step-by-step procedure; moreover, there can be no guarantee that a solution will be found. Here is an example of a problem that is unsolvable by an algorithm.

EXAMPLE 2.1 The halting problem

The problem is to predict whether a given computer program, with given input data, will eventually halt.

This is a very practical problem for us programmers: we all occasionally write a program that gets into a never-ending loop. One of the most famous results in computer science is that this problem cannot be solved by any algorithm. It turns out that any 'algorithm' that purports to solve this problem will itself get into a never-ending loop, for at (cast some programs that might be given to it. As we shall see later in this section, we insist that every algorithm must eventually terminate.

If we can never find an algorithm to predict whether a given program halts with given input data, we clearly can never find an algorithm to prove whether a given program behaves correctly fen- all possible input data.

It may still be possible for a human to prove that a particular program is correct. Indeed. this has been done for some important small programs and subprograms. But we can never automate such proofs of correctness.

In fact, many problems in mathematics and computer science are unsolvable by algorithms. In a way, this is rather reassuring: we can be sure that mathematicians and computer scientists will never be made redundant by machines!

From now on, we shall consider only problems that are solvable by algorithms.

Algorithms

Concerning al-orithirns themselves, we can state the following principles:

  • The algorithm will be performed by some processor, which may be a machine or a human.
  • The algorithm must be expressed in steps that the processor is capable of performing.
  • The algorithm must eventually terminate, producing the required answer.
Some algorithms, as we have already seen, are intended to be performed by humans rather than machines. But no algorithm is allowed to rely on qualities, such as insight and creativity, that distinguish humans from machines. This suggests a definition:

An algorithm is an automatic procedure for solving a stated problem, a procedure that could (at least in principle) be performed by a machine.

The principle that the algorithm must be expressed in steps that can be performed by the processor should now be clear. If the processor has to work out for itself what steps to follow, then what we have is not an algorithm. The principle that every algorithm must eventually terminate should also be clear. If it never terminates, it never produces an answer, therefore it is not an algorithm! So an algorithms must avoid getting into a never-ending loop...

Read More Show Less

Table of Contents

Preface.

Introduction.

Algorithms.

The Array Data Structure.

Linked-List Data Structures.

Abstract Data Types.

Stack Abstract Data Types.

Queue Abstract Data Types.

List Abstract Data Types.

Set Abstract Data Types.

Binary Tree Data Structures.

Map Abstract Data Types.

Hash-Table Data Structures.

Priority-Queue Abstract Data Types.

Tree Abstract Data Types.

Graph Abstract Data Types.

Balanced Search Treet Data Structures.

Conclusion.

Appendix A: Summary of Mathematics for Algorithm Analysis.

Appendix B: Summary of Java.

Appendix C: Summary of the Java Collections Framework.

Further Reading.

Index.

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously
Sort by: Showing 1 Customer Reviews
  • Anonymous

    Posted October 21, 2001

    The book is terrible

    It's all written back to front and it doesnt explain things clearly. If you're SUPER intellegent then this book might be ok, but if you're like me and just want to learn without headach, then find another book. This one is a joke...

    Was this review helpful? Yes  No   Report this review
Sort by: Showing 1 Customer Reviews

If you find inappropriate content, please report it to Barnes & Noble
Why is this product inappropriate?
Comments (optional)