126,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Data structures and algorithms is a fundamental course in Computer Science, which enables learners across any discipline to develop the much-needed foundation of efficient programming, leading to better problem solving in their respective disciplines. A Textbook of Data Structures and Algorithms is a textbook that can be used as course material in classrooms, or as self-learning material. The book targets novice learners aspiring to acquire advanced knowledge of the topic. Therefore, the content of the book has been pragmatically structured across three volumes and kept comprehensive enough to help them in their progression from novice to expert. With this in mind, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language. It includes 181 illustrative problems and 276 review questions to reinforce a theoretical understanding and presents a suggestive list of 108 programming assignments to aid in the implementation of the methods covered.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 256
Veröffentlichungsjahr: 2022
Ähnliche
Table of Contents
Cover
Series Page
Title Page
Copyright Page
Preface
About this edition
Organization of the book
Salient features of the book
Target audience
Acknowledgments
1 Introduction
1.1. History of algorithms
1.2. Definition, structure and properties of algorithms
1.3. Development of an algorithm
1.4. Data structures and algorithms
1.5. Data structures – definition and classification
1.6. Algorithm design techniques
1.7. Organization of the book
2 Analysis of Algorithms
2.1. Efficiency of algorithms
2.2. Apriori analysis
2.3. Asymptotic notations
2.4. Time complexity of an algorithm using the
O
notation
2.5. Polynomial time versus exponential time algorithms
2.6. Average, best and worst case complexities
2.7. Analyzing recursive programs
2.8. Illustrative problems
3 Arrays
3.1. Introduction
3.2. Array operations
3.3. Number of elements in an array
3.4. Representation of arrays in memory
3.5. Applications
3.6. Illustrative problems
4 Stacks
4.1. Introduction
4.2. Stack operations
4.3. Applications
4.4. Illustrative problems
5 Queues
5.1. Introduction
5.2. Operations on queues
5.3. Circular queues
5.4. Other types of queues
5.5. Applications
5.6. Illustrative problems
6 Linked Lists
6.1. Introduction
6.2. Singly linked lists
6.3. Circularly linked lists
6.4. Doubly linked lists
6.5. Multiply linked lists
6.6. Unrolled linked lists
6.7. Self-organizing lists
6.8. Applications
6.9. Illustrative problems
7 Linked Stacks and Linked Queues
7.1. Introduction
7.2. Operations on linked stacks and linked queues
7.3. Dynamic memory management and linked stacks
7.4. Implementation of linked representations
7.5. Applications
7.6. Illustrative problems
References
Index
Summary of Volume 2
Summary of Volume 3
Other titles frominComputer Engineering
End User License Agreement
List of Tables
Chapter 2
Table 2.1. Total frequency count of program segment A
Table 2.2 Total frequency count of program segment B
Table 2.3. Total frequency count of program segment C
Table 2.4. Comparison of polynomial time and exponential time algorithms
Table P2.4.
Frequency count of the statements in
procedure Fibonacci (n)
Table P2.7. Frequency count of the statements in the program fragment of Pro...
Chapter 4
Table 4.1.
Push/pop operations on stack DEVICE[1:3]
Chapter 5
Table 5.1.
Insert/delete operations on the queue BIRDS [1:3]
Table 5.2.
Insert and delete operations on the circular queue COLOURS [0:3]
...
Chapter 6
Table 6.1.
Student details for representation as a multiply linked list
Chapter 7
Table 7.1.
Insert and delete operations on linked stack DEVICE
Table 7.2.
Insert and delete operations on a linked queue BIRDS
Table 7.3.
Working of algorithm
BALANCE_EXPR ()
on the expression (A+B)* C
Table 7.4. Working of the algorithm BALANCE_EXPR () on the expression ((A+B)...
List of Illustrations
Chapter 1
Figure 1.1. Omnipresence of computers. see www.iste.co.uk/pai/algorithms1.zi...
Figure 1.2. Discipline of computer science from the perspective of problem s...
Figure 1.3. Algorithms and data structures for efficient problem solving usi...
Figure 1.4.
Classification of data structures
Chapter 2
Figure 2.1. Growth rate of some computing time functions. see www.iste.co.uk...
Figure 2.2.
Skeletal recursive procedures
Figure 2.3.
Tower of Hanoi puzzle (initial configuration)
Figure 2.4. Pictorial representation of the skeletal recursive procedure for...
Figure P2.10.
Tree of recursive calls for the recursive function GUESS(6,3)
...
Chapter 3
Figure 3.1.
Examples of arrays
Figure 3.2.
Array operations: store and retrieve
Figure 3.3.
Size of a two-dimensional array
Figure 3.4.
Size of a three-dimensional array
Figure 3.5. Viewing higher dimensional arrays in terms of their lower dimens...
Figure 3.6. Row-major order and column-major order of a two-dimensional arra...
Figure 3.7.
Representation of one-dimensional arrays in memory
Figure 3.8.
Representation of a two-dimensional array in memory
Figure 3.9.
Representation of three-dimensional arrays in the memory
Figure 3.10.
Matrix and a sparse matrix
Figure 3.11.
Sparse matrix representation
Figure 3.12.
String as an array of characters
Figure 3.13.
Array of strings
Chapter 4
Figure 4.1.
Stack and its functionality
Figure 4.2.
Common examples of a stack
Figure 4.3.
Array implementation of stacks
Algorithm 4.1.
Implementation of push operation on a stack
Algorithm 4.2.
Implementation of pop operation on a stack
Figure 4.4.
Recursive procedure to compute n!
Figure 4.5. Snapshots of the stack data structure during the execution of th...
Algorithm 4.3.
Procedure to evaluate a postfix expression E
Figure P4.1. Two stacks are stored in a single array A with the bottom of st...
Figure P4.2.
Snapshots of array A in illustrative problem 4.6
Figure P4.3. Two stacks stored in a single array A with their bottom of stac...
Figure P4.4.
Snapshots of array A in illustrative problem 4.7
Chapter 5
Figure 5.1.
A queue and its functionality
Figure 5.2.
Common examples of queues
Figure 5.3.
Array implementation of a queue
Algorithm 5.1.
Implementation of an insert operation on a queue
Algorithm 5.2.
Implementation of a delete operation on a queue
Figure 5.4.
Working of a circular queue
Figure 5.5. Circular movement of FRONT and REAR variables in a circular queu...
Figure 5.6.
Physical and conceptual view of a circular queue
Algorithm 5.3.
Implementation of insert operation in a circular queue
Algorithm 5.4.
Implementation of a delete operation in a circular queue
Figure 5.7.
A priority queue
Figure 5.8.
A stack, queue and a deque – a comparison
Figure 5.9.
A naive diagram of a time-sharing system
Figure 5.10. Time-sharing system simulation – non-priority-based job request...
Figure 5.11.
Snapshot of the queue at time 5, 10 and 14
Figure 5.12.
Simulation of the time-sharing system for priority-based jobs
Figure 5.13.
Snapshots of the priority queue at times 4, 8 and 12
Chapter 6
Figure 6.1. Drawbacks of sequential data structures – inefficient implementa...
Figure 6.2. Drawbacks of sequential data structures – inefficient storage me...
Figure 6.3.
A general structure of a node in a linked list
Figure 6.4.
A singly linked list and its node structure
Figure 6.5. A singly linked list – its logical and physical representation...
Figure 6.6.
Logical representation of insertion in a singly linked list
Algorithm 6.1. To insert a data element ITEM in a non-empty singly liked lis...
Algorithm 6.2.
To insert ITEM after node NODE in a singly linked list START
Figure 6.7. Insertion of APPOLLO and SOYUZ 4 in the SPACE_MISSION list shown...
Algorithm 6.3. Deletion of a node to the right of node NODEX in a singly lin...
Figure 6.8.
Logical representation of deletion in a singly linked list
Figure 6.9.
Deletion of CHANDRA and PLANCK from the SPACE-MISSION list
Figure 6.10.
Representation of a circular list
Figure 6.11.
A headed circularly linked list
Figure 6.12.
Insertion of MARUTI into the headed circularly linked list CARS
Figure 6.13.
Deletion of FORD from the headed circularly linked list CARS
Figure 6.14.
Some primitive operations on a circularly linked list P
Figure 6.15.
Concatenation of two circularly linked lists
Figure 6.16. Node structure of a doubly linked list and the various list typ...
Figure 6.17. The logical and physical representation of a circular doubly li...
Algorithm 6.4. To insert node X to the right of node Y in a headed circular ...
Algorithm 6.5.
Delete node X from a headed circular doubly linked list P
Figure 6.18.
Insertion/deletion in a headed circular doubly linked list
Figure 6.19.
Logical and physical representation of list PLANET
Figure 6.20.
Deletion of PLUTO and insertion of JUPITER in list PLANET
Figure 6.21.
The node structure of a multiply linked list
Figure 6.22.
Node structure of the multiply linked list STUDENT
Figure 6.23.
Multiply linked list structure of list STUDENT
Figure 6.24.
Insert ALI into the multiply linked list STUDENT
Figure 6.25. Delete REBECCA from the sports club membership list of the mult...
Figure 6.26.
Structure of a node in an unrolled linked list
Figure 6.27.
An example unrolled linked list
Figure 6.28.
Insertions in an unrolled linked list
Figure 6.29.
Deletions in an unrolled linked list
Figure 6.30. Addition of polynomials – node structure and singly linked list...
Figure 6.31.
Node structures of polynomials in two/three variables
Figure 6.32. A sparse matrix and the node structure for its representation a...
Figure 6.33. Multiply linked representation of the sparse matrix shown in Fi...
Figure P6.1. Insertion of NEW_DATA as the first element in a singly linked l...
Figure P6.2. Insertion of NEW_DATA as the kth element in a non-empty singly ...
Figure P6.3.
Deletion of last element in a singly linked list T
Figure P6.4. Calculation of length of a circularly linked list T with a head...
Figure P6.5.
A circular doubly linked list T with a head node
Figure P6.6(a) A circular doubly linked list T with missing DATA field value...
Figure P6.6(b)
Updated circular doubly linked list T
Figure P6.7. (a and b) Declaration of a node in a programming language and t...
Figure P6.7. (c–f) Logical representation of list T after execution of comma...
Figure P6.8.
Logical representations of a list T and the updated links
Figure P6.9.
Reversing a singly linked list by manipulating links
Figure P6.10. Swapping of elements in a singly linked list by manipulating l...
Figure P6.11.
A singly linked list with a cycle
Figure P6.12. Creation of an unrolled linked list and demonstration of inser...
Chapter 7
Figure 7.1 Stack and queue representations (conventional, sequential and lin...
Figure 7.2
Push and pop operations on a linked stack S
Figure 7.3
Insert and delete operations on the linked queue Q
Figure 7.4. Association between GETNODE () and RETURN () procedures and AVAI...
Figure 7.5. The scheme of reserved storage pool and free storage pool in the...
Figure 7.6. A snapshot of the memory accommodating a singly linked list in i...
Figure 7.7. Logical representation of the singly linked list and available s...
Figure 7.8.
Linked list representation of a polynomial
Figure 7.9. Linear queue representation of the polynomial 9x6 – 2x4 + 3x2 + ...
Figure P7.10.
Queue list: node structure, example and memory snapshot
Guide
Cover Page
Series Page
Title Page
Copyright Page
Preface
Acknowledgments
Table of Contents
Begin Reading
References
Index
Summary of Volume 2
Summary of Volume 3
Other titles from in Computer Engineering
WILEY END USER LICENSE AGREEMENT
Pages
ii
iii
iv
ix
x
xi
xii
xiii
xiv
xv
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
241
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
One of the greatest lessons I have learnt in my life is to pay as much attention to the means of work as to its end… I have been always learning great lessons from that one principle, and it appears to me that all the secret of success is there; to pay as much attention to the means as to the end…. Let us perfect the means; the end will take care of itself.
– Swami Vivekananda(Lecture Delivered at Los Angeles, California, January 4, 1900)
A Textbook of Data Structures and Algorithms 1
Mastering Linear Data Structures
G A Vijayalakshmi Pai
First published 2022 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Previous edition published in 2008 as “Data Structures and Algorithms: Concepts, Techniques and Applications” by McGraw Hill Education (India) Pvt Ltd. © McGraw Hill Education (India) Pvt Ltd. 2008
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
John Wiley & Sons, Inc.
27-37 St George’s Road
111 River Street
London SW19 4EU
Hoboken, NJ 07030
UK
USA
www.iste.co.uk
www.wiley.com
© ISTE Ltd 2022The rights of G A Vijayalakshmi Pai to be identified as the author of this work have been asserted by her in accordance with the Copyright, Designs and Patents Act 1988.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.
Library of Congress Control Number: 2022945771
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-78630-869-6
Preface
Efficient problem solving using computers, irrespective of the discipline or application, calls for the design of efficient algorithms. The inclusion of appropriate data structures is of critical importance to the design of efficient algorithms. In other words, good algorithm design must go hand in hand with appropriate data structures for an efficient program design to solve a problem.
Data structures and algorithms is a fundamental course in computer science, which most undergraduate and graduate programs in computer science and other allied disciplines in science and engineering offer during the early stages of the respective programs, either as a core or as an elective course. The course enables students to have a much-needed foundation for efficient programming, leading to better problem solving in their respective disciplines.
Most of the well-known text books/monographs on this subject have discussed the concepts in relation to a programming language – beginning with Pascal and spanning a spectrum of them such as C, C++, C#, Java, Python and so on, essentially calling for ample knowledge of the language, before one proceeds to try and understand the data structure. There does remain a justification in this. The implementation of data structures in the specific programming language need to be demonstrated or the algorithms pertaining to the data structures concerned need a convenient medium of presentation and when this is the case, why not a programming language?
Again, while some authors have insisted on using their books for an advanced level course, there are some who insist on a working knowledge of the specific programming language as a prerequisite to using the book. However, in the case of a core course, as it is in most academic programs, it is not uncommon for a novice or a sophomore to be bewildered by the “miles of code” that demonstrate or explain a data structure, rendering the subject difficult to comprehend. In fact, the efforts that one needs to put in to comprehend the data structure and its applications are distracted by the necessity to garner sufficient programming knowledge to follow the code. It is indeed ironic that while a novice is taught data structures to appreciate programming, in reality it turns out that one learns programming to appreciate data structures!
In my decades-old experience of offering the course to graduate programs, which admits students from diverse undergraduate disciplines, with little to no strong knowledge of programming, I had several occasions to observe this malady. In fact, it is not uncommon in some academic programs, especially graduate programs which, due to their shorter duration, have a course in programming and data structures running in parallel in the same semester, much to the chagrin of the novice learner! That a novice is forced to learn data structures through their implementation (in a specific programming language), when in reality it ought to be learning augmented with the implementation of the data structures, has been the reason behind the fallout.
A solution to this problem would be to
Frame the course such that the theory deals with the concepts, techniques and applications of data structures and algorithms, not taking recourse to any specific programming language, but instead settling for a pseudo-language, which clearly expounds the data structure. Additionally, supplementing the course material with illustrative problems, review questions and exercises to reinforce the students’ grasp of the concepts would help them gain useful insights while learning.
Augment the theory with laboratory sessions to enable the student to implement the data structure in itself or as embedded in an application, in the language of his/her own choice or as insisted upon in the curriculum. This would enable the student who has acquired sufficient knowledge and insight into the data structures to appreciate the beauty and merits of employing the data structure by programming it themself, rather than “look” for the data structure in a prewritten code.
This means that text books catering to the fundamental understanding of the data structure concepts for use as course material in the classroom are as much needed as the books that cater to the implementation of data structures in a programming language for use in the laboratory sessions. While most books in the market conform to the latter, bringing out a book to be classroom course material and used by instructors handling a course on data structures and algorithms, comprehensive enough for the novice students to benefit from, has been the main motivation in writing this book.
As such, the book details concepts, techniques and applications pertaining to data structures and algorithms, independent of any programming language, discusses several examples and illustrative problems, poses review questions to reinforce the understanding of the theory, and presents a suggestive list of programming assignments to aid implementation of the data structures and algorithms learned.
In fact, the book may either be independently used as a textbook since it is self-contained or serve as a companion for books discussing data structures and algorithms implemented in specific programming languages such as C, C++, Java, Python, and so on.
At this juncture, it needs to be pointed out that a plethora of programming resources and freely downloadable implementations of the majority of the data structures in almost all popular languages are available on the Internet, which can undoubtedly serve as good guides for the learner. However, it has to be emphasized that an earnest student of data structures and algorithms must invest a lot of time and self-effort in trying to implement the data structures and algorithms learned, in a language of one’s choice, all by oneself, in order to attain a thorough grasp of the concepts.
About this edition
This edition is a largely revised and enlarged version of its predecessor, published by McGraw Hill, USA. The earlier edition published in 2008 saw 15 reprints in its life span of 13 years (ending January 2022) and was recommended as a text book for the course in several universities and colleges. It comprised 17 chapters categorized into five parts and reinforced learning through 133 illustrative problems, 215 review questions and 74 programming assignments.
The features of this new edition are as follows:
There are 22 chapters spread across three volumes that detail sequential linear data structures, linked linear data structures, nonlinear data structures, advanced data structures, searching and sorting algorithms, algorithm design techniques and NP-completeness.
The data structures of
k
-d trees and treaps have been elaborated in a newly included chapter (Chapter 15) in Volume 3.
The data structures of strings, bit rays, unrolled linked lists, self-organizing linked lists, segment trees and
k
-ary trees have been introduced in the appropriate sections of the existing chapters in Volumes 1 and 2.
The concepts of counting binary search trees and Kruskal’s algorithm have been detailed in the appropriate sections of the existing chapters in Volume 2.
Skip list search, counting sort and bucket sort have been included in the chapters on searching and sorting algorithms in Volume 3.
The algorithm design techniques of divide and conquer, the greedy method and dynamic programming have been elaborately discussed in Chapters 19–21 in Volume 3.
The concept of NP-completeness has been detailed in a newly included chapter, Chapter 22 in Volume 3.
Several illustrative problems, review questions and programming assignments have been added to enrich the content and aid in understanding the concepts. The new edition thus includes 181 illustrative problems, 276 review questions and 108 programming assignments.
Organization of the book
The book comprises three volumes, namely, Volume 1: Chapters 1–7, Volume 2: Chapters 8–12 and Volume 3: Chapters 13–22.
Volume 1 opens with an introduction to data structures and concepts pertaining to the analysis of algorithms, detailed in Chapters 1 and 2, which is essential to appreciate the theories and algorithms related to data structures and their applications.
Chapters 3–5 detail sequential linear data structures, namely, arrays, strings, bit arrays, stacks, queues, priority queues and dequeues, and their applications. Chapters 6 and 7 elucidate linked linear data structures, namely linked lists, linked stacks and linked queues, and their applications.
Volume 2 details nonlinear data structures. Chapters 8 and 9 elaborate on the nonlinear data structures of trees, binary trees and graphs, and their applications. Chapters 10–12 highlight the advanced data structures of binary search trees, AVL trees, B trees, tries, red-black trees and splay trees, and their applications.
Volume 3 details an assortment of data structures, algorithm design strategies and their applications.
Chapters 13–15 discuss hash tables, files, k-d trees and treaps. Chapter 16 discusses the search algorithms of linear search, transpose sequential search, interpolation search, binary search, Fibonacci search, skip list search and other search techniques.
Chapter 17 elaborates on the internal sorting algorithms of bubble sort, insertion sort, selection sort, merge sort, shell sort, quick sort, heap sort, radix sort, counting sort and bucket sort, and Chapter 18 discusses the external sorting techniques of sorting with tapes, sorting with disks, polyphase merge sort and cascade merge sort.
Chapters 19–21 detail the algorithm design strategies of divide and conquer, the greedy method and dynamic programming and their applications.
Chapter 22 introduces the theories and concepts of NP-completeness.
For a full list of the contents of Volumes 2 and 3, see the summary at the end of this book.
Salient features of the book
The features of the book are as follows:
all-around emphasis on theory, problems, applications and programming assignments;
simple and lucid explanation of the theory;
inclusion of several applications to illustrate the use of data structures and algorithms;
several worked-out examples as illustrative problems in each chapter;
list of programming assignments at the end of each chapter;
review questions to strengthen understanding;
self-contained text for use as a text book for either an introductory or advanced level course.
Target audience
The book could be used both as an introductory or an advanced-level textbook for undergraduate, graduate and research programs, which offer data structures and algorithms as a core course or an elective course. While the book is primarily meant to serve as a course material for use in the classroom, it could be used as a companion guide during the laboratory sessions to nurture better understanding of the theoretical concepts.
An introductory level course for a duration of one semester or 60 lecture hours, targeting an undergraduate program or first-year graduate program or a diploma program or a certificate program, could include Chapters 1–7 of Volume 1, Chapter 8 of Volume 2, Chapters 13, 16 (sections 16.1, 16.2, 16.5) and 17 (sections 17.1–17.3, 17.5, 17.7) of Volume 3 in its curriculum.
A middle-level course for a duration of one semester or 60 lecture hours targeting senior graduate-level programs and research programs such as MS/PhD could include Chapters 1–7 of Volume 1, Chapters 8–11 of Volume 2, Chapter 13 and selective sections of Chapters 16–17 of Volume 3.
An advanced level course that focuses on advanced data structures and algorithm design could begin with a review of Chapter 8 and include Chapters 9–12 of Volume 2, Chapters 14 and 15 and selective sections of Chapters 16–18, and Chapters 19–22 of Volume 3 in its curriculum based on the level of prerequisite courses satisfied.
Chapters 8–10 and Chapter 11 (sections 11.1–11.3) of Volume 2 and Chapters 13, 14 and 18 of Volume 3 could be useful to include in a curriculum that serves as a prerequisite for a course on database management systems.
To re-emphasize, all theory sessions must be supplemented with laboratory sessions to encourage learners to implement the concepts learned in an appropriate language that adheres to the curricular requirements of the programs concerned.
Acknowledgments
The author is grateful to ISTE Ltd., London, UK, for accepting to publish the book, in collaboration with John Wiley & Sons Inc., USA. She expresses her appreciation to the publishing team, for their professionalism and excellent production practices, while bringing out this book in three volumes.
The author expresses her sincere thanks to the Management and Principal, PSG College of Technology, Coimbatore, India for the support extended while writing the book.
The author would like to place on record her immense admiration and affection for her father, Late Professor G. A. Krishna Pai and her mother Rohini Krishna Pai for their unbounded encouragement and support to help her follow her life lessons and her sisters Dr. Rekha Pai and Udaya Pai, for their unstinted, anywhere-anytimeanything kind of help and support, all of which were instrumental and inspirational in helping this author create this work.
G. A. Vijayalakshmi PaiAugust 2022
1Introduction
While looking around and marveling at the technological advancements of this world – both within and without, one cannot help but perceive the intense and intrinsic association of the disciplines of science and engineering and their allied and hybrid counterparts, with the ubiquitous machines called computers. In fact, it is difficult to spot a discipline that has distanced itself from the discipline of computer science. To quote a few, be it a medical surgery or diagnosis performed by robots or doctors on patients halfway across the globe, or the launching of space crafts and satellites into outer space, or forecasting tornadoes and cyclones, or the more mundane needs of the online reservation of tickets or billing at supermarkets, or the control of washing machines, etc., one cannot help but deem computers to be omnipresent, omnipotent, why even omniscient! (Figure 1.1).
In short, any discipline that calls for problem solving using computers looks up to the discipline of computer science for efficient and effective methods of solving the problems in their respective fields. From the view point of problem solving, the discipline of computer science could be naively categorized into the following four sub areas, notwithstanding the overlaps, extensions and gray areas within themselves:
Machines
