scientific article; zbMATH DE number 108394

Publication date 23 January 1993

abstract data types analysis of algorithms ANSI C data structures design of algorithms discrete mathematics graphs and algorithms hash table priority queues sorting trees

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

The textbook contains an exposition of the most fundamental topics concerning the analysis of data structures and algorithms. It is written at the level of undergraduate students and offers a coherent introduction for all those who wish to enter this field of research. The book is organized in eleven main parts: Introduction (Chapter 1), Algorithm Analysis (Chapter 2), Lists, Stacks, and Queues (Chapter 3), Trees (Chapter 4), Hashing (Chapter 5), Priority Queues (Heaps) (Chapter 6), Sorting (Chapter 7), The Disjoint Set ADT (Chapter 8), Graph Algorithms (Chapter 9), Algorithm Design Techniques (Chapter 10) and Amortized Analyses (Chapter 11). In the first two parts, the author discusses the aims of the book and presents a brief review of programming concepts and discrete mathematics with respect to the analysis of algorithms. All these concepts are explained by illustrative examples. The third chapter is devoted to three of the most simple and basic data structures. Also, the author introduces basic notions like abstract data types (ADT) and various types of linked lists. In Chapter 4, the author looks at the simple data strucure `Tree', especially at binary search trees, expression trees, AVL-Trees, Splay- Trees and B-Trees. The Chapters 5 and 6 cover the ADT's `hash table' and `Priority Queues'. The author presents several methods of implementing hash tables, compares these methods analytically and gives numerous applications of hashing. He looks at efficient and advanced implementations of the ADT `Priority Queue' (various types of heaps, binomial queue). In Chapter 7, internal and external sorting are investigated. All important general-purpose sorting algorithms are discussed and analyzed: Insertion sort, Shellsort, Heapsort, Mergesort, Quicksort, Bucket sort etc. In Chapter 8, the author describes an efficient data structure to solve the equivalence problem for relations. For the disjoint set ADT, he shows how it can be implemented with minimal coding effort; furthermore, he analyzes the running time of the implementation and considers simple applications. The following Chapter 9 is devoted to several problems in graph theory. The author presents common representations of graphs and algorithms for the solution of typical problems: Single-Source Shortest-Path Problem, All-Pairs Shortest Path Problem, Network-Flow Problems, Minimum Spanning Tree Problem, etc. All of the standard algorithms are presented along with appropriate data structures and analysis of running time. In Chapter 10, the author switches his attention from the implementation of algorithms to the design of algorithms. He discusses greedy algorithms, the technique `divide and conquer', dynamic programming, randomized and backtracking algorithms. All these concepts are explained by illustrative examples. The last Chapter 11 is devoted to the amortized analysis of the running time for several data structures presented in the Chapters 4 and 6. Essentially, the author deals with binomial queues, skew heaps, Fibonacci heaps and splay trees. The algorithms are presented in ANSI C. Each of the eleven chapters concludes with an extensive list of references indicating the author's sources, and a selection of informative exercises. These references and exercises also represent extensions and improvements to the results given in the text. This monograph is written in a simple and clear way and it is delightful to read. The textbook offers valuable insight into the implementation, the design and the analysis of algorithms and data structures. It is highly recommended for undergraduate students.

Cited in

(14)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023852)