Data Structures and Algorithms.pdf

Data Structures and Algorithms 1 A Study Guide for Students of Sorsogon State University - Bulan Campus2 Jarrian Vince G. Gojar3 September 19, 2024 1 A course in the Bachelor of Science...

Data Structures and Algorithms 1 A Study Guide for Students of Sorsogon State University - Bulan Campus2 Jarrian Vince G. Gojar3 September 19, 2024 1 A course in the Bachelor of Science in Computer Science/Information Technology/Information Systems program. 2 This book is a study guide for students of Sorsogon State University - Bulan Campus taking up the course Data Structures and Algorithms. 3 https://github.com/godkingjay Sorsogon State University - Bulan Campus Contents Contents ii List of Figures ix List of Tables x 1 Introduction to Data Structures and Algorithms 2 1.1 Introduction....................................... 2 1.2 Setup and Installation................................. 2 1.2.1 C++ Compiler Installation.......................... 2 1.2.1.1 Windows............................... 2 1.2.2 Visual Studio Code Installation........................ 3 1.2.3 Testing the Installation............................ 3 1.3 What are Data Structures?.............................. 4 1.4 What are Algorithms?................................. 4 1.5 Why Study Data Structures and Algorithms?.................... 4 1.6 Basic Terminologies.................................. 4 1.6.1 Data....................................... 4 1.6.2 Data Object................................... 4 1.6.3 Data Type................................... 4 1.6.3.1 Primitive Data Types........................ 5 1.6.3.1.1 Integer (int)........................ 5 1.6.3.1.2 Character (char)...................... 5 1.6.3.1.3 Boolean (bool)....................... 5 1.6.3.1.4 Floating-Point (float)................... 5 1.6.3.1.5 Double (double)...................... 6 1.6.3.2 Non-primitive Data Types..................... 6 1.6.3.2.1 Array (int, float, char, etc.)................ 6 1.6.3.2.2 String (char)........................ 6 1.6.3.2.3 Structure.......................... 6 1.6.3.2.4 Class............................ 7 1.6.3.2.5 Vector............................ 7 1.6.3.2.6 List............................. 7 1.6.3.2.6.1 Singly Linked List................. 7 1.6.3.2.6.2 Doubly Linked List................ 8 1.6.3.2.6.3 Circular Linked List................ 8 1.6.3.2.6.4 Circular Doubly Linked List........... 8 1.6.3.2.7 Stack............................ 9 1.6.3.2.8 Queue............................ 9 1.6.3.2.8.1 Circular Queue................... 9 ii CONTENTS iii 1.6.3.2.8.2 Priority Queue................... 9 1.6.3.2.8.3 Double-Ended Queue (Deque).......... 10 1.6.3.2.9 Tree............................. 10 1.6.3.2.10 Graph............................ 10 1.6.3.2.11 Hash Map or Hash Table................. 11 1.6.3.2.12 Set............................. 11 1.6.4 Abstract Data Type.............................. 12 1.6.5 Pointers..................................... 12 1.6.5.1 Declaring Pointers.......................... 13 1.6.5.2 Initializing Pointers......................... 13 1.6.5.3 Dereferencing Pointers........................ 13 1.6.5.4 Pointer Arithmetic.......................... 14 1.6.5.5 Pointer to Pointer.......................... 14 1.7 Asymptotic Notations................................. 15 1.7.1 Big-O Notation................................. 15 1.7.2 Omega Notation................................ 15 1.7.3 Theta Notation................................. 16 1.7.4 Complexity of an Algorithm.......................... 16 1.7.4.1 Time Complexity.......................... 16 1.7.4.1.1 Constant Time Complexity (O(1))............ 16 1.7.4.1.2 Logarithmic Time Complexity (O(log n))........ 17 1.7.4.1.3 Linear Time Complexity (O(n))............. 17 1.7.4.1.4 Linearithmic Time Complexity (O(n log n))....... 17 1.7.4.1.5 Quadratic Time Complexity (O(n2 ))........... 18 1.7.4.1.6 Exponential Time Complexity (O(2n ))......... 19 1.7.4.1.7 Factorial Time Complexity (O(n!))........... 19 1.7.4.2 Space Complexity.......................... 19 1.7.4.2.1 Constant Space Complexity (O(1))........... 19 1.7.4.2.2 Linear Space Complexity (O(n))............. 20 1.7.4.2.3 Quadratic Space Complexity (O(n2 )).......... 20 1.7.4.2.4 Exponential Space Complexity (O(2n ))......... 21 1.7.4.2.5 Factorial Space Complexity (O(n!))........... 21 1.8 Summary........................................ 21 1.9 Coding Exercises.................................... 22 2 Arrays and Linked Lists 23 2.1 Introduction....................................... 23 2.2 Arrays.......................................... 23 2.2.1 Types of Arrays................................ 25 2.2.1.1 One-dimensional Array....................... 25 2.2.1.2 Multi-dimensional Array...................... 26 2.2.2 Array Operations................................ 28 2.2.2.1 Insertion............................... 28 2.2.2.2 Deletion................................ 28 2.2.2.3 Searching............................... 28 2.2.3 Complexity Analysis of Arrays........................ 28 2.3 Linked Lists....................................... 28 2.3.1 Types of Linked Lists............................. 28 2.3.1.1 Singly Linked List.......................... 28 2.3.1.2 Doubly Linked List......................... 28 2.3.1.3 Circular Linked List......................... 28 CONTENTS iv 2.3.2 Operations on Linked Lists.......................... 28 2.3.2.1 Insertion............................... 28 2.3.2.2 Deletion................................ 28 2.3.2.3 Searching............................... 28 2.3.3 Complexity Analysis of Linked Lists..................... 28 2.4 Comparison of Arrays and Linked Lists....................... 28 2.5 Summary........................................ 28 3 Stacks and Queues 29 3.1 Introduction....................................... 30 3.2 Stacks.......................................... 30 3.2.1 Operations on Stacks.............................. 30 3.2.1.1 Push................................. 30 3.2.1.2 Pop.................................. 30 3.2.1.3 Peek.................................. 30 3.2.1.4 isEmpty................................ 30 3.2.1.5 isFull................................. 30 3.2.2 Complexity Analysis of Stacks........................ 30 3.2.3 Implementation of Stacks Using Arrays................... 30 3.2.4 Implementation of Stacks Using Linked Lists................ 30 3.3 Queues.......................................... 30 3.3.1 Types of Queues................................ 30 3.3.1.1 Linear Queue............................. 30 3.3.1.2 Circular Queue............................ 30 3.3.1.3 Priority Queue............................ 30 3.3.1.4 Double-ended Queue (Deque).................... 30 3.3.2 Operations on Queues............................. 30 3.3.2.1 Enqueue............................... 30 3.3.2.2 Dequeue............................... 30 3.3.2.3 Front................................. 30 3.3.2.4 Rear.................................. 30 3.3.3 Complexity Analysis of Queues........................ 30 3.3.4 Implementation of Queues Using Arrays................... 30 3.3.5 Implementation of Queues Using Linked Lists................ 30 3.4 Comparison of Stacks and Queues.......................... 30 3.5 Summary........................................ 30 4 Trees 31 4.1 Introduction....................................... 32 4.2 Properties of Trees................................... 32 4.2.1 Root Node................................... 32 4.2.2 Parent Node.................................. 32 4.2.3 Child Node................................... 32 4.2.4 Leaf Node.................................... 32 4.2.5 Ancestors.................................... 32 4.2.6 Siblings..................................... 32 4.2.7 Descendants................................... 32 4.2.8 Height of a Tree................................ 32 4.2.9 Depth of a Node................................ 32 4.2.10 Degree of a Node................................ 32 4.2.11 Level of a Node................................. 32 4.2.12 Subtree..................................... 32 CONTENTS v 4.3 Types of Trees..................................... 32 4.3.1 Binary Tree................................... 32 4.3.1.1 Types of Binary Trees........................ 32 4.3.1.1.1 Left-skewed Binary Tree................. 32 4.3.1.1.2 Right-skewed Binary Tree................. 32 4.3.1.1.3 Complete Binary Tree................... 32 4.3.2 Ternary Tree.................................. 32 4.3.3 N-ary Tree................................... 32 4.3.4 Binary Search Tree............................... 32 4.3.5 AVL Tree.................................... 32 4.3.6 Red-Black Tree................................. 32 4.4 Basic Operations on Trees............................... 32 4.4.1 Creation of a Tree............................... 32 4.4.2 Insertion..................................... 32 4.4.3 Deletion..................................... 32 4.4.4 Searching.................................... 32 4.4.5 Traversal.................................... 32 4.4.5.1 Preorder Traversal.......................... 32 4.4.5.2 Inorder Traversal........................... 32 4.4.5.3 Postorder Traversal......................... 32 4.4.5.4 Level-order Traversal........................ 32 4.5 Complexity Analysis of Trees............................. 32 4.6 Summary........................................ 32 5 Graphs 33 5.1 Introduction....................................... 34 5.2 Properties of Graphs.................................. 34 5.2.1 Vertex...................................... 34 5.2.2 Edge....................................... 34 5.2.3 Degree of a Vertex............................... 34 5.2.4 Path....................................... 34 5.3 Types of Graphs.................................... 34 5.3.1 Finite Graph.................................. 34 5.3.2 Infinite Graph................................. 34 5.3.3 Trivial Graph.................................. 34 5.3.4 Simple Graph.................................. 34 5.3.5 Multi Graph.................................. 34 5.3.6 Null Graph................................... 34 5.3.7 Complete Graph................................ 34 5.3.8 Pseudo Graph................................. 34 5.3.9 Regular Graph................................. 34 5.3.10 Bipartite Graph................................ 34 5.3.11 Labelled Graph................................. 34 5.3.12 Weighted Graph................................ 34 5.3.13 Directed Graph................................. 34 5.3.14 Undirected Graph............................... 34 5.3.15 Connected Graph................................ 34 5.3.16 Disconnected Graph.............................. 34 5.3.17 Cyclic Graph.................................. 34 5.3.18 Acyclic Graph................................. 34 5.3.19 Directed Acyclic Graph (DAG)........................ 34 CONTENTS vi 5.3.20 Digraph..................................... 34 5.3.21 Subgraph.................................... 34 5.4 Operations on Graphs................................. 34 5.4.1 Creation of a Graph.............................. 34 5.4.2 Insertion..................................... 34 5.4.2.1 Insertion of a Vertex......................... 34 5.4.2.2 Insertion of an Edge......................... 34 5.4.3 Deletion..................................... 34 5.4.3.1 Deletion of a Vertex......................... 34 5.4.3.2 Deletion of an Edge......................... 34 5.4.4 Traversal.................................... 34 5.4.4.1 Depth First Search (DFS)...................... 34 5.4.4.2 Breadth First Search (BFS)..................... 34 5.4.5 Shortest Path.................................. 34 5.4.6 Minimum Spanning Tree............................ 34 5.5 Complexity Analysis of Graphs............................ 34 5.6 Summary........................................ 34 6 Sorting and Searching 35 6.1 Introduction....................................... 36 6.2 Sorting.......................................... 36 6.2.1 Types of Sorting Algorithms......................... 36 6.2.1.1 Bubble Sort............................. 36 6.2.1.2 Selection Sort............................ 36 6.2.1.3 Insertion Sort............................ 36 6.2.1.4 Merge Sort.............................. 36 6.2.1.5 Quick Sort.............................. 36 6.2.1.6 Heap Sort............................... 36 6.2.1.7 Radix Sort.............................. 36 6.2.1.8 Counting Sort............................ 36 6.2.1.9 Bucket Sort.............................. 36 6.2.2 Comparison of Sorting Algorithms...................... 36 6.3 Searching........................................ 36 6.3.1 Types of Searching Algorithms........................ 36 6.3.1.1 Linear Search............................. 36 6.3.1.2 Binary Search............................ 36 6.3.1.3 Jump Search............................. 36 6.3.1.4 Interpolation Search......................... 36 6.3.1.5 Exponential Search......................... 36 6.3.1.6 Fibonacci Search........................... 36 6.3.1.7 Ternary Search............................ 36 6.3.2 Comparison of Searching Algorithms..................... 36 6.4 Summary........................................ 36 7 Hashing 37 7.1 Introduction....................................... 37 7.2 Hash Table....................................... 37 7.3 Hash Function..................................... 37 7.4 Collision Resolution Techniques............................ 37 7.4.1 Separate Chaining............................... 37 7.4.2 Open Addressing................................ 37 7.4.2.1 Linear Probing............................ 37 CONTENTS vii 7.4.2.2 Quadratic Probing.......................... 37 7.4.2.3 Double Hashing........................... 37 7.5 Complexity Analysis of Hashing............................ 37 7.6 Summary........................................ 37 8 Advanced Data Structures and Algorithms 38 8.1 Introduction....................................... 39 8.2 Advanced Data Structures............................... 39 8.2.1 Segment Tree.................................. 39 8.2.2 Fenwick Tree.................................. 39 8.2.3 Suffix Tree................................... 39 8.2.4 Suffix Array................................... 39 8.2.5 Trie....................................... 39 8.2.6 Heap....................................... 39 8.2.7 Disjoint Set................................... 39 8.2.8 Skip List.................................... 39 8.2.9 Splay Tree.................................... 39 8.2.10 Bloom Filter.................................. 39 8.2.11 KD Tree..................................... 39 8.2.12 Quad Tree.................................... 39 8.2.13 Octree...................................... 39 8.2.14 B-Tree...................................... 39 8.2.15 B+ Tree..................................... 39 8.2.16 R-Tree...................................... 39 8.2.17 X-Tree...................................... 39 8.2.18 Y-Tree...................................... 39 8.2.19 Z-Tree...................................... 39 8.3 Advanced Algorithms.................................. 39 8.3.1 Dynamic Programming............................ 39 8.3.2 Greedy Algorithms............................... 39 8.3.3 Backtracking.................................. 39 8.3.4 Divide and Conquer.............................. 39 8.3.5 Branch and Bound............................... 39 8.3.6 Randomized Algorithms............................ 39 8.3.7 Approximation Algorithms.......................... 39 8.3.8 String Matching Algorithms.......................... 39 8.3.9 Pattern Searching Algorithms......................... 39 8.3.10 Cryptography Algorithms........................... 39 8.3.11 Geometric Algorithms............................. 39 8.3.12 Graph Algorithms............................... 39 8.3.13 Network Flow Algorithms........................... 39 8.3.14 Game Theory Algorithms........................... 39 8.3.15 Quantum Algorithms............................. 39 8.4 Summary........................................ 39 9 Applications of Data Structures and Algorithms 40 9.1 Applications in Computer Science........................... 41 9.1.1 Operating Systems............................... 41 9.1.2 Database Management Systems........................ 41 9.1.3 Compiler Design................................ 41 9.1.4 Networking................................... 41 9.1.5 Artificial Intelligence.............................. 41 CONTENTS viii 9.1.6 Machine Learning............................... 41 9.1.7 Computer Graphics.............................. 41 9.1.8 Computer Vision................................ 41 9.1.9 Robotics..................................... 41 9.1.10 Web Development............................... 41 9.1.11 Mobile Development.............................. 41 9.1.12 Game Development.............................. 41 9.1.13 Cybersecurity.................................. 41 9.1.14 Quantum Computing............................. 41 9.2 Applications in Real Life................................ 41 9.2.1 Social Media.................................. 41 9.2.2 E-commerce................................... 41 9.2.3 Healthcare................................... 41 9.2.4 Finance..................................... 41 9.2.5 Transportation................................. 41 9.2.6 Education.................................... 41 9.2.7 Agriculture................................... 41 9.2.8 Manufacturing................................. 41 9.2.9 Entertainment................................. 41 9.2.10 Sports...................................... 41 9.2.11 Travel...................................... 41 9.2.12 Telecommunications.............................. 41 9.2.13 Energy...................................... 41 9.2.14 Environment.................................. 41 9.2.15 Politics..................................... 41 9.2.16 Military..................................... 41 9.3 Summary........................................ 41 10 References 42 List of Figures 1 Pointer Example.................................... 12 2 Dereferencing Pointers................................. 13 3 Pointer Arithmetic................................... 14 4 Pointer to Pointer................................... 15 5 Asymptotic Notation.................................. 16 6 Elements of an array in C++............................. 23 7 Initializing Array Elements.............................. 24 8 Initializing Array Elements with Empty Members.................. 25 9 One-dimensional Array in C++............................ 26 10 Two-dimensional Array in C++............................ 26 ix List of Tables x List of Codes 1.1 Hello World Program.................................. 3 1.2 Compiling the Program................................ 3 1.3 Running the Program................................. 3 1.4 Integer Data Type................................... 5 1.5 Character Data Type.................................. 5 1.6 Boolean Data Type................................... 5 1.7 Floating-Point Data Type............................... 5 1.8 Double Data Type................................... 6 1.9 Array Data Type.................................... 6 1.10 String Data Type.................................... 6 1.11 Structure Data Type.................................. 6 1.12 Class Data Type.................................... 7 1.13 Vector Data Type................................... 7 1.14 List Data Type..................................... 7 1.15 Singly Linked List Data Type............................. 8 1.16 Doubly Linked List Data Type............................ 8 1.17 Circular Linked List Data Type............................ 8 1.18 Circular Doubly Linked List Data Type....................... 8 1.19 Stack Data Type.................................... 9 1.20 Queue Data Type.................................... 9 1.21 Priority Queue Data Type............................... 10 1.22 Deque Data Type.................................... 10 1.23 Tree Data Type..................................... 10 1.24 Graph Data Type.................................... 11 1.25 Ordered Map Data Type................................ 11 1.26 Unordered Map Data Type.............................. 11 1.27 Ordered Set Data Type................................ 11 1.28 Unordered Set Data Type............................... 12 1.29 Pointer Data Type................................... 12 1.30 Declaring Pointers................................... 13 1.31 Initializing Pointers................................... 13 1.32 Dereferencing Pointers................................. 13 1.33 Pointer Arithmetic................................... 14 1.34 Pointer to Pointer Data Type............................. 15 1.35 Constant Time Complexity.............................. 16 1.36 Logarithmic Time Complexity............................. 17 1.37 Linear Time Complexity................................ 17 1.38 Linearithmic Time Complexity............................ 17 1.39 Quadratic Time Complexity.............................. 18 1.40 Exponential Time Complexity............................. 19 1.41 Factorial Time Complexity.............................. 19 xi LIST OF CODES xii 1.42 Constant Space Complexity.............................. 19 1.43 Linear Space Complexity............................... 20 1.44 Quadratic Space Complexity............................. 20 1.45 Exponential Space Complexity............................ 21 1.46 Factorial Space Complexity.............................. 21 2.1 Array Declaration................................... 23 2.2 Assigning Values to Array Elements......................... 24 2.3 Initializing Array Elements.............................. 24 2.4 Initializing Array Elements with Unspecified Size.................. 24 2.5 Initializing Array Elements with Empty Members.................. 25 2.6 One-dimensional Array................................. 26 2.7 Two-dimensional Array................................. 26 2.8 Two-dimensional Array with Empty Members.................... 27 Preface “Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” – Linus Torvalds Jarrian Vince G. Gojar https://github.com/godkingjay 1 1 Introduction to Data Structures and Algorithms 1.1 Introduction Data structures and algorithms are one of the fundamental components of computer science. They are essential for solving complex problems efficiently and effectively. Data structures are used to store and organize data in a computer so that it can be accessed and manipulated efficiently. Algorithms are step-by-step procedures or formulas for solving a problem. They are the instructions that tell a computer how to perform a task. In this course, we will learn about the fundamental data structures and algorithms that are used in computers. We will study how to design, implement, and analyze data structures and algorithms to solve real-world problems. By the end of this course, you will have a solid foundation in data structures and algorithms that will help you become a better programmer and problem solver. 1.2 Setup and Installation In this course, we will be using the C++ programming language to implement data structures and algorithms. C++ is a powerful and versatile programming language that is widely used in the field of computer science. To get started, you will need to install a C++ compiler and an integrated development environment (IDE) on your computer. 1.2.1 C++ Compiler Installation The first step is to install a C++ compiler on your computer. A compiler is a program that translates source code written in a programming language into machine code that can be executed by a computer. There are several C++ compilers available, but we recommend using the GNU Compiler Collection (GCC) which is a free and open-source compiler that supports multiple programming languages including C++. 1.2.1.1 Windows To install GCC on Windows, you can use the MinGW (Minimalist GNU for Windows) project which provides a port of GCC to Windows. You can download the MinGW installer from the MinGW website and follow the installation instructions. You can install MinGW 2  1.2. SETUP AND INSTALLATION 3 by following the instructions here: https://code.visualstudio.com/docs/languages/cpp# _example-install-mingwx64-on-windows 1.2.2 Visual Studio Code Installation The next step is to install an integrated development environment (IDE) on your computer. An IDE is a software application that provides comprehensive facilities to computer programmers for software development. We recommend using Visual Studio Code which is a free and open-source IDE developed by Microsoft. You can download Visual Studio Code from the official website and follow the installation instructions: https://code.visualstudio.com/Download Other than Visual Studio Code, you also need to install the C/C++ extension for Visual Studio Code. You can install the C/C++ extension by following the instructions here: https: //code.visualstudio.com/docs/languages/cpp 1.2.3 Testing the Installation To test if the installation was successful, you can create a simple C++ program and compile it using the C++ compiler. Open Visual Studio Code and create a new file with the following C++ code: 1 #include 2 namespace std; 3 4 int main() { 5 cout