Advanced Programming and Problem-Solving Strategies in C. Part IV: Exam-Based Problems.

Previous parts provide a comprehensive introduction to a C language syntax, and a modern study of computer algorithms and data structures. Following these parts, this book presents many solutions to problem-based examinations using the C language. Problems are extracted from examination tests of the "Algorithms and programming" course delivered within the Computer Engineering and Electronic and Communication Engineering bachelor-level degree at Politecnico di Torino. The text is intended primarily for use in undergraduate or graduate courses in algorithms and data structures. The content of the previous parts should be considered as prerequisites for reading this book. We have attempted to make every problem accessible and interesting. We also provide careful explanations of the main mathematical and algorithmic issues. The volume is divided into two chapters. The first one includes only completely solved examination-based problems. These correspond to 16 examination tests, i.e., 16 simplified and 16 standard examination tests, for a total of 64 completely solved exercises. The second chapter includes only suggested problems, taken from 12 mock examination-based tests, again each one including a simplified and a standard section, for a total of 48 suggested problems. Simplified exercises target the guided development of the solution to a problem, with only a small emphasis on design and problem-solving skills and more emphasis on the ability to use advanced C features (pointers, dynamic allocation, recursion) and on the knowledge of basic data structures and algorithms. For those simplified problems, only the code required by the examination specification is reported in the text, i.e., clients, data definitions and data initialization are often not reported in the book for the sake of space. Standard exercises target the design and development of a program in C to solve a problem, the main emphasis being on the algorithm and data-structure adopted, and on problem-solving and design skills. As in the examination of "Algorithms and programming", exercises mainly include the following topics: Sorting, static and dynamic data structures, recursion, abstract objects, collections of objects and abstract data types (ADTs), trees, symbol tables (such as Binary Search Trees, BSTs, and Hash Tables), and graphs. Solution style follows the ones introduced in previous volumes by the same author. Solutions are usually introduced by short descriptions, illustrating the main philosophy and core ideas behind them. Simplified specifications (but sometimes even standard ones) may be followed by more than one solution, illustrating the main logic possibilities to reach the same final target. C syntax is somehow restricted to a minimum set of constructs, avoiding useless or redundant ones. Solution design is maintained as simple as possible, keeping in mind asymptotic time and memory costs. Each solution can be mono or multi-file. In this last case, book sub-titles specify the file name to correctly follow the inclusion of header files and type definitions. The book is also covered by online material, as all source codes are available on the editor web page. Among the main source references let us remind the following. As far as algorithms and data structure are concerned, the reader may refer to [1, 2, 3, 4, 5, 6]. For the C language and language syntax a few references are the following [7, 8, 9, 10, 11, 12]. We would sincerely appreciate any comments, criticisms, corrections and suggestions for improving the text. Please address all correspondence to: stefano.quer@polito.it or visits the following web page: http://fmgroup.polito.it/quer/ Changes for the second edition The book did not change much from the first edition. A summary of the most significant changes for the second edition is the following: . We added two new suggested exams at the end of Chapter 2. . We went through the entire book and rewrote sentences, paragraphs, and sections to make the writing clearer and more active. When necessary, we added new examples. . We deeply revised all C solutions, with particular care at the most complex ones, such as the ones involving graphs and aggregated data structures. We also revised many comments inserted into our code. . We corrected several errors and discrepancies. Most of these errors were discovered using the previous edition in class during lectures and practice tests.