JNTU Study Material For Data Structures (Computer Science Engineering)

About this eBook

Chapter 1
Introduction 1.1
What this book is, and what it isn t
This book provides implementations of common and uncommon algorithms in pseudocode which is language independent and provides for easy porting to most imperative programming languages. It is not a de nitive book on the theory of data structures and algorithms. For the most part this book presents implementations devised by the authors themselves based on the concepts by which the respective algorithms are based upon so it is more than possible that our implementations di er from those considered the norm. You should use this book alongside another on the same subject, but one that contains formal proofs of the algorithms in question. In this book we use the abstract big Oh notation to depict the run time complexity of algorithms so that the book appeals to a larger audience.
1.2
Assumed knowledge
We have written this book with few assumptions of the reader, but some have been necessary in order to keep the book as concise and approachable as possible. We assume that the reader is familiar with the following 1. Big Oh notation 2. An imperative programming language 3. Object oriented concepts
1.2.1
Big Oh notation
For run time complexity analysis we use big Oh notation extensively so it is vital that you are familiar with the general concepts to determine which is the best algorithm for you in certain scenarios. We have chosen to use big Oh notation for a few reasons, the most important of which is that it provides an abstract measurement by which we can judge the performance of algorithms without using mathematical proofs. 1
CHAPTER 1. INTRODUCTION
2
Figure 1.1 Algorithmic run time expansion Figure 1.1 shows some of the run times to demonstrate how important it is to choose an e cient algorithm. For the sanity of our graph we have omitted cubic O n3 , and exponential O 2n run times. Cubic and exponential algorithms