** Book: **
This book is designed as an introductory text book for the Data Structures and Algorithms course. Data structures and algorithms is a standard course taught in many universities teaching computer engineering and/or computer science. In general, an introduction to programming course is taught as a prerequisite before the data structures course, and afterwards an algorithm course is taught to complete the problem solving objective.
The book is designed as a 40 hour course work. An example course schedule can be designed as: Link list, tree, graph and sorting algorithms require 6 hours; algorithm analysis, stack, queue, hashing, and disjoint set require 3 hours. The first chapter of the book gives an introductory info about algorithm analysis, afterwards the main data structures are explained in the coming 8 chapters (from chapter 2 to chapter 9). Although the last chapter, i.e. sorting algorithms, is not a data structure, it is included since sorting is taught in many universities as a part of this course.

** Contents **

- 1 Algorithm Analysis
- 1.1 Big-O Notation 1
- 1.2 Analysis of Non-recursive Algorithms 5
- 1.3 Analysis of Recursive Algorithms 8
- 1.4 Master Theorem 12
- 1.5 Notes 14
- 1.6 Solved Exercises 13
- 1.7 Exercises 17

- 2 Linked List
- 2.1 Definition 24
- 2.2 Singly Linked List Operations 27
- 2.3 Merging Two Singly Linked Lists 36
- 2.4 Doubly Linked List 38
- 2.5 Doubly Linked List Operations 41
- 2.6 Circular Linked List 50
- 2.7 Application: Polynom Arithmetic 55
- 2.8 Solved Exercises 64
- 2.9 Exercises 69

- 3 Stack
- 3.1 Array Implementation 73
- 3.2 Linked List Implementation 78
- 3.3 Application: Evaluating Mathematical Expressions 82
- 3.4 Solved Exercises 92
- 3.5 Exercises 94

- 4 Queue
- 4.1 Array Implementation 100
- 4.2 Linked List Implementation 103
- 4.3 Application: Darts 107
- 4.4 Solved Exercises 110
- 4.5 Exercises 114

- 5 Binary Search Trees
- 5.1 Definition 118
- 5.2 Binary Search Tree Operations 122
- 5.3 Traversals 132
- 5.4 Non-recursive Traversal 134
- 5.5 AVL Trees 137
- 5.6 B+ Tree 149
- 5.7 Application: Tree Index 158
- 5.8 Notes 164
- 5.9 Solved Exercises 164
- 5.10 Exercises 169

- 6 Hashing
- 6.1 Hash Table 173
- 6.2 Separate Chaining 176
- 6.3 Open Addressing 180
- 6.4 Rehashing 186
- 6.5 Application: Dart 187
- 6.6 Application: Hash Index 190
- 6.7 Notes 192
- 6.8 Solved Exercises 192
- 6.9 Exercises 196

- 7 Heap
- 7.1 Definition 201
- 7.2 Heap Operations 203
- 7.3 d-ary Heap 211
- 7.4 Application: Dart 221
- 7.5 Notes 223
- 7.6 Solved Exercises 223
- 7.7 Exercises 225

- 8 Disjoint Set
- 8.1 Definition 229
- 8.2 Disjoint Set Operations 232
- 8.3 Application: Cracking the Code 235
- 8.4 Solved Exercises 238
- 8.5 Exercises 241

- 9 Graph
- 9.1 Definition 247
- 9.2 Add Edge 250
- 9.3 Application: Connected Components 252
- 9.4 Application: Shortest Path 260
- 9.5 Application: Minimum Spanning Tree 270
- 9.6 Notes 280
- 9.7 Solved Exercises 281
- 9.8 Exercises 285

- 10 Sorting Algorithms
- 10.1 Insertion Sort 290
- 10.2 Selection Sort 292
- 10.3 Buble Sort 293
- 10.4 Shell Sort 295
- 10.5 Heap Sort 298
- 10.6 Merge Sort 302
- 10.7 Quick Sort 305
- 10.8 Bucket Sort 308
- 10.9 Radix Sort 310
- 10.10 Notes 312
- 10.11 Solved Exercises 312
- 10.12 Exercises 316