ISBN 9789350235553,Data Structure & Algorithm

Data Structure & Algorithm



Shroff Publishers & Distributors Pvt Ltd

Publication Year 2012

ISBN 9789350235553

ISBN-10 9350235552


Number of Pages 492 Pages
Language (English)

Computer And Internet

In recent years the subject of computer programming has been recognized as a discipline whose mastery is fundamental and crucial to the success of many engineering projects and which is amenable to scientific treatment and presentation. It has advanced from a craft to an academic discipline. The initial outstanding contributions toward this development were made by E.W. Dijkstra and C.A.R. Hoare. Dijkstra's Notes on Structured Programming [1] opened a new view of programming as a scientific subject and intellectual challenge, and it coined the title for a "revolution" in programming. Hoare's Axiomatic Basis of Computer Programming [2] showed in a lucid manner that programs are amenable to an exacting analysis based on mathematical reasoning. Both these papers argue convincingly that many programmming errors can be prevented by making programmers aware of the methods and techniques which they hitherto applied intuitively and often unconsciously. These papers focused their attention on the aspects of composition and analysis of programs, or more explicitly, on the structure of algorithms represented by program texts. Yet, it is abundantly clear that a systematic and scientific approach to program construction primarily has a bearing in the case of large, complex programs which involve complicated sets of data. Hence, a methodology of programming is also bound to include all aspects of data structuring. Programs, after all, are concrete formulations of abstract algorithms based on particular representations and structures of data. An outstanding contribution to bring order into the bewildering variety of terminology and concepts on data structures was made by Hoare through his Notes on Data Structuring [3]. It made clear that decisions about structuring data cannot be made without knowledge of the algorithms applied to the data and that, vice versa, the structure and choice of algorithms often depend strongly on the structure of the underlying data. In short, the subjects of program composition and data structures are inseparably intertwined. Yet, this book starts with a chapter on data structure for two reasons. First, one has an intuitive feeling that data precede algorithms: you must have some objects before you can perform operations on them. Second, and this is the more immediate reason, this book assumes that the reader is familiar with the basic notions of computer programming. Traditionally and sensibly, however, introductory programming courses concentrate on algorithms operating on relatively simple structures of data. Hence, an introductory chapter on data structures seems appropriate. About the Author Prof. Maria S. Rukadikar has earned M-Tech degree in Computer science from JNTU, Hyderabad and currently working as a Professor, in RAIT, Nerul, Navi Mumbai. She has 7 years of experience in academic. She got inspiration from her father to write this book. She is an author of technical books. She started her academic career at Govt. College of Engg., Karad as an Associate and Junior Faculty. Table of Contents Chapter 1. Design & Analysis of Algorithm 1.1 Introduction 1.2 Complexity 1.2.1 Space Complexity 1.2.2 Time Complexity 1.3 Asymptotic Notations 1.3.1 Big-O Notation 1.3.2 Omega Notation Chapter 2. Searching and Sorting 2.1 Searching with Analysis 2.1.1 Linear Search 2.1.2 Binary Search 2.2 Sorting with Analysis 2.2.1 Bubble Sort 2.2.2 Selection Sort 2.2.3 Insertion Sort 2.2.4 Shell Sort 2.2.5 Quick Sort 2.2.6 Merge Sort 2.2.7 Heap Sort 2.2.8 Radix Sort Chapter 3. Hashing 3.1 Introduction: Terminologies 3.2 Hash Function 3.3 Hash (Sparse) Tables 3.4 Collision Methods 3.4.1 Collision Resolution with (linear probing by Open Addressing) 3.4.2 Quadratic Probing 3.4.3 Collision Resolution by Chaining 3.5 Comparision of Method Chapter 4. Trees 4.1 Introduction - Definition 4.2 Types of Tree 4.3 Binary Tree 4.3.1 Binary Tree Representations 4.3.2 Binary Tree Traversal 4.4 Binary Search Tree 4.4.1 Analysis of Bst Operations 4.5 Threaded Binary Tree 4.5.1 Threaded Tree Traversal 4.5.2 Insertion and Deletion in Threaded Tree Chapter 5. Multiway Tree 5.1 Multiway Search Tree - Introduction 5.1.1 Searching a Multi-Way Tree 5.1.2 Traversing a Multi-Way Tree 5.1.3 Insertion in a Multi-Way Tree 5.1.4 Deletion in Multiway Tree 5.2 B-Trees 5.3 B+-Trees 5.4 Difference Between B-Tree and B+Tree Chapter 6. Height Balance Tree 6.1 AVL Tree 6.2 Rotation of AVL Tree 6.2.1 Single Rotation of AVL Tree: 6.2.2 Double Rotation of AVL Tree: 6.3 Insertion of Node in Avl Tree 6.4 Deletion of Node in AVL Tree 6.5 Height of an AVL Tree Chapter 7. Graph 7.1 Introduction: 7.2 Directed and Undirected Graphs 7.3 Computer Representations of Graph 7.4 Graph Traversal Method 7.4.1 DEPTH-FIRST SEARCH (DFS): 7.4.2 BREADTH-FIRST TRAVERSAL: 7.5 Topological Sort 7.6 Application: Shortest path using Dijkstra's Algorithm