Picsart Academy’s Library

Data Abstraction and Problem Solving with C++

F. M. Carrano, J. J. Prichard

If you associate the words “recursion” and “abstraction” with a nightmare, it is the right time to read this book. It will help you see things are not as bad as they seem.

The book we are going to speak about will help the students juggle the problem-solving and programming techniques, valuing both processes equally as they form a computer scientist’s toolkit.

The book covers the analytical methods of developing programs using thematic, simple examples. Abstraction, gradual refinement of algorithms and data structures, and recursion are the principal approaches used to solve the problems in the book.
The book that inspired Carrano and Prichard is “Walls and Mirrors”, written by professors Helman and Veroff. They used the analogy of walls and mirrors, which made the book special by facilitating material presentation and making the whole information more understandable.

The walls and mirrors mentioned in the title present two main methods of solving problems; data abstraction isolates and hides module implementation details from the rest of the program, just like the walls separate and hide you from your curious neighbors, while recursion is an approach that reduces the initial problem into similar, but smaller problems just like the mirrors reduce the image with each new reflection.

The book will help you learn object-oriented programming, data abstraction basics, and other modern methods of solving problems.

It is intended for readers familiar with the C++ programming language basics.
To understand the book, it is enough to know about if and switch conditional operators, for, while and do loops, transfer options of functions and arguments, arrays, lines, structures, and files.

Those who are not familiar with recursive functions but have heard much about them and somehow managed not to like them can find the detailed description of those functions in the 2nd and 5th chapters, as well as learn about classes (1st, 3rd, and 8th chapters), inheritance, virtual functions, and templates.
All of the above mentioned are closely correlated to the implementation of abstract data types (ATD) in the form of classes where the emphasis is right on the abstraction rather than C++ language features.

It is important to note that the whole material is presented in the context of object-oriented programming. Besides, the book includes a brief introduction to Unified Modeling Language. It is up to you to choose the topics and sequence.

You can find the interdependencies between chapters in the diagram.

The book consists of two parts:

Part 1 includes the fundamental problems of programming and software development.

The next chapter discusses recursion and the benefits of recursive thinking skills for computer scientists. Chapter 3 describes the abstraction principles and thoroughly covers abstract data types (ATD). This chapter also presents C++ language classes used to implement ADTs. Chapter 4 presents the indicators, linked lists, and their role in implementing abstract data types. Template classes, C++ Standard template library (STL), containers, and iterators are also discussed in this chapter.

Part 2 presents solutions to problems using abstract data types.

It continues observing abstraction as a method of solving problems. For the first time, the leading abstract data types are presented: stack, queue, binary tree, binary search tree, heap, and queue with priorities. These types are implemented as classes.
Chapter 8 provides details on classes, inheritance, template classes, and iterators. Friend classes and virtual functions are also presented. Chapter 9 introduces algorithms. The effectiveness of several search and sorting algorithms is analyzed, including recursive merge and quick sort. Part 2 also contains more advanced topics such as balanced search trees (2–3, 2–3–4, red-black, and AVL trees) and hashing.

Data storage methods are discussed at the end of the book and merge sort, external hashing, and B-tree indexes are covered. These search algorithms generalize internal hashing schemes and previously described 2–3 trees.

Thus, the book helps students learn to integrate problem-solving and programming skills, focusing on thought processes and methods used by computer scientists.

Enjoy your reading!