Data Structure and Algorithms in Java From Basics to Expert Proficiency (William Smith) (Z-Library)

Data Structure and Algorithms in Java From Basics to Expert Proficiency Copyright © 2024 by HiTeX Press All rights reserved. No part of this publication may be reproduced, distributed, or transmitted in any form or by any means, including photocopying, recording, or other electronic or mechanical methods, without the prior written permission of the publisher, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law.

Contents 1 Introduction to Data Structures and Algorithms   1.1 What are Data Structures?   1.2 What are Algorithms?   1.3 Importance of Data Structures and Algorithms in Computer Science   1.4 Types of Data Structures   1.5 Types of Algorithms   1.6 Analyzing Algorithms: Time and Space Complexity   1.7 Big O Notation: An Overview   1.8 Choosing the Right Data Structure for Your Problem   1.9 Real-world Applications of Data Structures and Algorithms   1.10 Future Trends in Data Structures and Algorithms 2 Java Basics for Data Structures and Algorithms   2.1 Introduction to Java   2.2 Setting Up Your Development Environment   2.3 Basic Syntax and Structure of Java Programs   2.4 Variables, Data Types, and Operators   2.5 Control Flow Statements (if, else, switch)   2.6 Loops (for, while, do-while)   2.7 Methods and Modular Programming   2.8 Object-Oriented Programming in Java   2.9 Working with Arrays and Collections   2.10 Handling Exceptions   2.11 Java Standard Library Overview   2.12 Writing and Running Java Programs 3 Arrays and Strings   3.1 Introduction to Arrays   3.2 One-dimensional Arrays   3.3 Multi-dimensional Arrays   3.4 Dynamic Arrays   3.5 Array Operations: Insertion and Deletion

  3.6 Array Traversal   3.7 Array Searching Algorithms   3.8 Array Sorting Algorithms   3.9 Introduction to Strings   3.10 String Operations and Manipulations   3.11 String Searching Algorithms   3.12 String Comparison and Palindromes 4 Linked Lists   4.1 Introduction to Linked Lists   4.2 Singly Linked Lists   4.3 Doubly Linked Lists   4.4 Circular Linked Lists   4.5 Linked List Operations: Insertion   4.6 Linked List Operations: Deletion   4.7 Traversing a Linked List   4.8 Searching in a Linked List   4.9 Reversing a Linked List   4.10 Detecting and Removing Loops in a Linked List   4.11 Intersection and Merging of Linked Lists 5 Stacks and Queues   5.1 Introduction to Stacks   5.2 Stack Operations: Push, Pop, Peek   5.3 Implementing Stacks using Arrays   5.4 Implementing Stacks using Linked Lists   5.5 Applications of Stacks: Balanced Parentheses   5.6 Applications of Stacks: Infix, Prefix, and Postfix Expressions   5.7 Introduction to Queues   5.8 Queue Operations: Enqueue, Dequeue, Front, Rear   5.9 Implementing Queues using Arrays   5.10 Implementing Queues using Linked Lists   5.11 Circular Queues   5.12 Double-ended Queues (Deques)   5.13 Priority Queues 6 Recursion   6.1 Introduction to Recursion

  6.2 Base Case and Recursive Case   6.3 Visualizing Recursion with Examples   6.4 Recursion vs Iteration   6.5 Problems Solvable by Recursion   6.6 Recursive Algorithms: Factorial   6.7 Recursive Algorithms: Fibonacci Sequence   6.8 Recursive Algorithms: Towers of Hanoi   6.9 Backtracking: An Introduction   6.10 Common Pitfalls and How to Avoid Them   6.11 Optimizing Recursive Solutions   6.12 Tail Recursion 7 Trees and Binary Search Trees   7.1 Introduction to Trees   7.2 Tree Terminology   7.3 Binary Trees   7.4 Tree Traversal Algorithms: In-order, Pre-order, Post-order   7.5 Binary Search Trees (BST)   7.6 Operations on BST: Insertion   7.7 Operations on BST: Deletion   7.8 Operations on BST: Searching   7.9 Balancing Binary Search Trees   7.10 Self-Balancing BST: AVL Trees   7.11 Self-Balancing BST: Red-Black Trees   7.12 Applications of Trees in Computer Science 8 Heaps and Priority Queues   8.1 Introduction to Heaps   8.2 Heap Properties and Types   8.3 Binary Heaps   8.4 Heap Operations: Insertion   8.5 Heap Operations: Deletion   8.6 Building a Heap   8.7 Heap Sort Algorithm   8.8 Introduction to Priority Queues   8.9 Implementing Priority Queues using Heaps   8.10 Applications of Heaps and Priority Queues   8.11 D-ary Heaps

  8.12 Fibonacci Heaps 9 Hashing and Hash Tables   9.1 Introduction to Hashing   9.2 Hash Functions   9.3 Collision Resolution Techniques: Separate Chaining   9.4 Collision Resolution Techniques: Open Addressing   9.5 Linear Probing   9.6 Double Hashing   9.7 Rehashing   9.8 Hash Table Operations: Insertion, Deletion, Searching   9.9 Applications of Hash Tables   9.10 Advantages and Disadvantages of Hashing 10 Graphs and Graph Algorithms   10.1 Introduction to Graphs   10.2 Graph Terminology   10.3 Graph Representations: Adjacency Matrix and Adjacency List   10.4 Graph Traversal Algorithms: Depth-First Search (DFS)   10.5 Graph Traversal Algorithms: Breadth-First Search (BFS)   10.6 Shortest Path Algorithms: Dijkstra’s Algorithm   10.7 Shortest Path Algorithms: Bellman-Ford Algorithm   10.8 Minimum Spanning Tree Algorithms: Prim’s Algorithm   10.9 Minimum Spanning Tree Algorithms: Kruskal’s Algorithm   10.10 Topological Sorting   10.11 Graph Coloring   10.12 Applications of Graph Algorithms

Introduction Data structures and algorithms are fundamental concepts in computer science and essential tools for software development. Proficiency in these areas enables developers to design, implement, and optimize efficient software that can handle complex tasks and large data sets. This book, "Data Structure and Algorithms in Java: From Basics to Expert Proficiency," is intended to provide a comprehensive guide to understanding and mastering these critical topics, all while using the Java programming language. In the realm of computer science, data structures refer to the systematic way of organizing and storing data so that it can be accessed and modified efficiently. Familiarity with various data structures and their appropriate applications is crucial for crafting performance-efficient software solutions. Algorithms, on the other hand, are definite procedures or formulas for solving problems. They describe a sequence of steps that need to be performed to reach a particular goal. The study of algorithms involves understanding their design, analysis of their efficiency, and the contexts in which they can be most effectively applied. The importance of data structures and algorithms extends beyond academic study and is crucial in practical, day-to-day programming tasks. Whether you are designing software that needs to process large amounts of data in real-time, implementing complex features such as search and sort operations, or optimizing existing code, a solid understanding of these concepts is indispensable. This book is structured into meticulously chosen chapters that build upon each other, ensuring a coherent and progressive learning experience. We begin by introducing the fundamental concepts of data structures and algorithms and move on to delve into specific types such as arrays, linked lists, stacks, queues, trees, heaps, and more. In the process, we will explore various algorithmic techniques including sorting, searching, and traversal, all illustrated with practical examples and Java code snippets.

Given the critical role of the Java programming language in this book, an early chapter is devoted to Java basics, ensuring that readers are comfortable with necessary Java syntax and features. This foundational knowledge is vital as we demonstrate the implementation of various data structures and algorithms in Java in the subsequent chapters. Each chapter is designed to be self-contained, providing thorough explanations, code examples, and exercises to reinforce the concepts learned. Our goal is to ensure that by the end of this book, readers will have developed a deep understanding of data structures and algorithms, and the ability to apply this knowledge to solve real-world problems efficiently using Java. This book is ideal for students, software developers, and anyone looking to deepen their understanding of data structures and algorithms. It serves as both a learning resource and a reference guide, suitable for individuals at different stages of their programming journey. In conclusion, mastering data structures and algorithms is pivotal for anyone seeking to excel in computer science and software development. This book is crafted to equip you with the knowledge and skills necessary to understand, implement, and optimize these core components of programming, all through the lens of Java. We invite you to immerse yourself in this comprehensive study, confident that it will significantly enhance your problem-solving capabilities and programming proficiency.

Chapter 1 Introduction to Data Structures and Algorithms Data structures and algorithms are the cornerstone of efficient programming in computer science. Understanding what they are, their types, and their importance lays the foundation for more advanced concepts. This chapter delves into the essential definitions, the critical role they play in software development, and offers an overview of different data structures and algorithms. It also introduces fundamental concepts such as time and space complexity and Big O notation, providing a clear understanding of how to analyze the efficiency of algorithms. 1.1 What are Data Structures? Data structures are specialized formats for organizing, processing, retrieving, and storing data. They are fundamental to designing efficient algorithms and effective programs. The choice of a suitable data structure can make a substantial difference in the performance and scalability of the software. Definition: A data structure is a systematic way to organize data in order to use it efficiently for various operations. Classification: Data structures can generally be classified into two main categories: Primitive Data Structures: These include basic types and are directly operated upon by machine instructions. Examples include integers, floats, characters, and pointers. Non-primitive Data Structures: These are more complex structures that are derived from primitive data structures. They are further classified into linear and non-linear data structures. Linear Data Structures: In a linear data structure, elements form a sequence or a linear list. Each element is connected to its previous and next element. They are easy to implement because of their organized structure. Examples include arrays, linked lists, stacks, and queues. An array is a collection of elements identified by index or key. Arrays allow constant-time access to elements, given their index. However, inserting or deleting elements can be costly since it may require shifting elements. // Java Implementation of an Array  int[] array = new int[10];  array[0] = 1;  array[1] = 2;  // Accessing elements  System.out.println(array[0]); // Output: 1 A linked list consists of nodes where each node contains a data field and a reference (or link) to the next node in the sequence. It is dynamic in nature, allowing for efficient insertions and deletions. // Java Implementation of a Singly Linked List Node  class Node {     int data;     Node next;     Node(int data) {        this.data = data; 

      this.next = null;     }  } Stacks follow the Last In First Out (LIFO) principle. Operations include push (insert), pop (delete), and peek (retrieve the top element). // Java Implementation of a Stack using Array  class Stack {     int top;     int capacity;     int[] stack;       Stack(int size) {        top = -1;        capacity = size;        stack = new int[capacity];     }       void push(int data) {        if (top == capacity - 1) {           System.out.println("Stack overflow");           return;        }        stack[++top] = data;     }       int pop() {        if (top == -1) {           System.out.println("Stack underflow");           return -1;        }        return stack[top--];     }       int peek() {        if (top == -1) {           System.out.println("Stack is empty");           return -1;        }        return stack[top];     }  } Queues follow the First In First Out (FIFO) principle. Operations include enqueue (insert) and dequeue (delete). // Java Implementation of a Queue using Linked List  class Queue {     Node front, rear;   

   Queue() {        front = rear = null;     }       void enqueue(int data) {        Node temp = new Node(data);        if (rear == null) {           front = rear = temp;           return;        }        rear.next = temp;        rear = temp;     }       int dequeue() {        if (front == null) {           return -1;        }        int data = front.data;        front = front.next;        if (front == null) {           rear = null;        }        return data;     }  } Non-linear Data Structures: In these structures, data elements are not organized in a sequence. Examples include trees and graphs. A tree is a hierarchical structure where each node contains a value and references to its children. One of the most common types of trees is the binary tree, where each node has at most two children. // Java Implementation of a Binary Tree Node  class TreeNode {     int data;     TreeNode left, right;       TreeNode(int item) {        data = item;        left = right = null;     }  } Graphs consist of nodes (vertices) and edges (connections between nodes). They are used to represent networks and relationships. Graphs can be directed or undirected, and can include cycles. // Java Implementation of a Graph using Adjacency List  class Graph {     private int V; // Number of vertices     private LinkedList<Integer> adj[]; // Adjacency lists 

     Graph(int v) {        V = v;        adj = new LinkedList[v];        for (int i = 0; i < v; ++i)           adj[i] = new LinkedList();     }       void addEdge(int v, int w) {        adj[v].add(w); // Add w to v’s list.     }  } Each type of data structure has specific usage scenarios, strengths, and weaknesses. For example, linked lists are suitable for applications where frequent insertions and deletions occur, but arrays are preferred when constant-time access to elements is required. Choosing the appropriate data structure requires considering factors such as the operations to be performed, memory usage, and the complexity of each operation. Deciding the correct data structure for a given problem is a critical skill for software engineers and computer scientists, enabling the creation of efficient and maintainable code. 1.2 What are Algorithms? An algorithm is a finite sequence of well-defined instructions typically used to solve a class of specific problems or to perform a computation. Algorithms are cornerstone elements of computer science and are implemented within programs to execute defined tasks. Their structured nature allows for reproducibility, reliability, and efficiency, which are crucial for developing robust software systems. An algorithm transforms input data into a specified output through a series of computational steps. Each step must be unambiguously defined, executable, and lead the problem closer to a solution. The efficiency and effectiveness of an algorithm are gauged by analyzing its time and space complexity. Consider a basic example, the algorithm for finding the maximum value in an array of integers. The algorithm iterates through each element, maintaining a record of the largest observed value: public class MaxValueAlgorithm {     public static int findMax(int[] numbers) {        int max = Integer.MIN_VALUE; // Start with the smallest possible integer        for (int number : numbers) {           if (number > max) {              max = number;           }        }        return max;     }  }

In this example, numbers is an array of integers, and the findMax method iterates through each integer in the array to determine the maximum value. This straightforward approach is foundational in understanding more complex algorithms. Algorithms can be categorized based on various criteria such as their purpose, implementation strategy, and design paradigm. Below are some significant categories: Sorting Algorithms: Algorithms intended to reorder elements in a list into a particular order, such as ascending or descending. Examples include QuickSort, MergeSort, and BubbleSort. public class BubbleSort {     public static void bubbleSort(int[] arr) {        int n = arr.length;        for (int i = 0; i < n-1; i++) {           for (int j = 0; j < n-i-1; j++) {              if (arr[j] > arr[j+1]) {                 int temp = arr[j];                 arr[j] = arr[j+1];                 arr[j+1] = temp;              }           }        }     }  } Search Algorithms: Techniques to find specific elements within a data structure. Examples include Binary Search and Linear Search. public class BinarySearch {     public static int binarySearch(int[] arr, int key) {        int low = 0;        int high = arr.length - 1;        while (low <= high) {           int mid = (low + high) / 2;           if (arr[mid] < key) {              low = mid + 1;           } else if (arr[mid] > key) {              high = mid - 1;           } else {              return mid; // key found           }        }        return -1; // key not found     }  } Graph Algorithms: Methods used for tasks such as traversing or searching graph data structures. Examples include Breadth-First Search (BFS), Depth-First Search (DFS), and Dijkstra’s Algorithm. Dynamic Programming: A methodology for solving complex problems by breaking them into simpler subproblems and storing the results of these subproblems to avoid redundant computations. Examples include Fibonacci sequence calculation and the Knapsack problem.

public class Fibonacci {     public static int fibonacci(int n) {        int[] fib = new int[n+1];        fib[0] = 0;        fib[1] = 1;        for (int i = 2; i <= n; i++) {           fib[i] = fib[i-1] + fib[i-2];        }        return fib[n];     }  } Greedy Algorithms: Approaches that make locally optimal choices at each step, intending to find the global optimum. Examples include the activity selection problem and Prim’s algorithm for finding the Minimum Spanning Tree. Algorithms are not limited to these categories and can be hybrid, combining elements from different paradigms to optimize their performance based on the problem context. To formalize an algorithm, pseudocode or formal programming languages are used. Pseudocode provides a high-level description of the algorithm that is clear and easy to understand but omits specific syntax details of a programming language. This makes it excellent for teaching and documenting as it conveys the logical flow and structure without syntactic distractions. Here is an example of pseudocode for the insertion sort algorithm: ___________________________________________________________ Algorithm 1: Insertion Sort Pseudocode__________________________________ Input: An array A of n integers Output: The array A sorted in ascending order for  i ← 1 to n − 1 do for  j ← i to 1 downto 1 do if  A[j] < A[j − 1] then swap( A[j],A[j − 1] ); end else break; end end end _____________________________________________________________________________ Algorithm analysis considers both the time complexity, which measures the number of operations an algorithm performs relative to the input size, and the space complexity, which measures the amount of memory an algorithm requires during its execution. These metrics provide insights into the efficiency and scalability of algorithms. Understanding algorithms involves not just knowing how they work but also when and why to use them in practice. This requires recognizing the nature of the problem, the properties of the data involved, and the performance requirements. Mastery of algorithms ultimately enables the design of efficient and effective computational solutions. 1.3 Importance of Data Structures and Algorithms in Computer Science In computer science, data structures and algorithms are fundamental concepts that underlie the creation of effective and efficient software. The importance of these topics cannot be overstated, as they play a critical role in determining the performance and scalability of applications. To understand their significance, we must examine several key areas where they make a substantial impact. One of the primary reasons data structures and algorithms are crucial is their influence on the efficiency of software operations. Suppose a program requires the frequent retrieval and update of

data. In that case, the choice of the correct data structure, such as hash tables for constant-time data access or balanced binary search trees for logarithmic-time queries, will dramatically affect the execution speed. Efficient algorithms further complement this by reducing the number of computational steps required to achieve a task, producing efficient and high-performing code. This directly translates into faster applications with reduced resource consumption, which is vital in both small-scale and large-scale systems alike. To illustrate the difference that a well-considered choice of data structure and algorithm can make, consider the example of sorting a list of integers. A naive approach using the bubble sort algorithm, which has a time complexity of O(n2), may be suitable for small lists. However, as the list grows, this approach becomes impractical. In contrast, an algorithm like quicksort, with an average time complexity of O(nlog n), will perform significantly better on larger datasets. This reduction in time complexity leads to substantial performance gains, highlighting the importance of selecting the right algorithm for a given task. Another vital aspect is the maintainability and scalability of code. By employing appropriate data structures and algorithms, developers can create code that is more modular and easier to understand, thereby simplifying debugging and maintenance tasks. For example, using a well-defined tree structure to represent hierarchical data can make traversal and manipulation operations straightforward. This clarity in code structure reduces complexities during updates or extensions to the software, leading to more scalable and adaptable systems. Furthermore, understanding data structures and algorithms enhances problem-solving skills by providing systematic approaches to tackling computational problems. It involves recognizing patterns and leveraging existing structures and techniques to devise optimal solutions. A computer scientist equipped with this knowledge can abstract complex problems into simpler sub-problems, identify the most effective data structures and algorithms to address these sub-problems, and combine them into comprehensive solutions. Additionally, the relevance of data structures and algorithms extends to resource optimization. Many modern applications run in resource-constrained environments, where efficient use of memory and processing power is crucial. For instance, embedded systems, mobile apps, and IoT devices all benefit from carefully chosen data structures and algorithms that minimize memory usage and processing cycles. This is pertinent in scenarios where hardware capabilities are limited, and optimizing software performance can mean the difference between functional and non-functional applications. Beyond immediate technical benefits, mastery of data structures and algorithms is also highly valued in the industry. It is a core competency that many employers look for during technical interviews. The ability to reason about and implement efficient solutions to algorithmic and data structure problems is a skill set that is synonymous with computer science proficiency. This aptitude is essential not just for creating performant software but also for participating in cutting-edge research and development, contributing to advancements in fields such as artificial intelligence, machine learning, and data science. In real-world applications, the importance of data structures and algorithms is evident in various domains. Search engines, databases, operating systems, networking components, and even simple web applications leverage these concepts to function efficiently. For example, databases use indexed data structures like B-trees to speed up query processing, while network routers use shortest-path algorithms to determine the most efficient routing of data packets. Each of these applications

demonstrates how critical data structures and algorithms are to the efficient functioning of systems that we rely on daily. Considering future trends, the importance of data structures and algorithms will only grow. As we encounter increasingly large datasets and more complex problems, the demand for optimized computational solutions will continue to rise. Innovations in quantum computing and parallel processing are poised to introduce new paradigms of problem solving, yet the foundational knowledge of data structures and algorithms will remain indispensable. Achieving breakthroughs in these advanced areas will still require a profound understanding of how information is organized and manipulated effectively. Understanding the importance of data structures and algorithms is not only about recognizing their utility but also about appreciating their foundational principles in computer science. This insight enables the development of robust, efficient, and scalable software that meets the needs of diverse applications, both now and in the future. 1.4 Types of Data Structures Data structures are essential constructs that enable efficient storage, retrieval, and modification of data. They can be broadly categorized into two main types: linear and non-linear data structures. Each type has various implementations and use cases. In this section, we explore both categories, along with specific examples and their applications. Linear Data Structures: Linear data structures organize elements sequentially, where each element is linked to its previous and next element. Common linear data structures include arrays, linked lists, stacks, and queues. Arrays: Arrays are collections of elements, typically of the same data type, stored in contiguous memory locations. Arrays allow random access to elements using an index. For example:    int[] numbers = {10, 20, 30, 40, 50};     int number = numbers[2]; // Accesses the third element, which is 30 Arrays are efficient for indexed access but have limitations in terms of dynamic resizing and insertion and deletion operations, which can be costly as it may require shifting elements. Linked Lists: A linked list is a collection of nodes where each node contains a data element and a reference (or link) to the next node in the sequence. There are various types of linked lists: singly linked lists, doubly linked lists, and circular linked lists. For example:    class Node {        int data;        Node next;          Node(int d) {           data = d;           next = null;        }     } 

     Node head = new Node(10);     head.next = new Node(20);     head.next.next = new Node(30); Linked lists are advantageous for dynamic memory allocation and frequent insertion and deletion operations. However, they do not support random access, so traversal from the head node is required to access elements. Stacks: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Elements can be added (pushed) or removed (popped) only from the top of the stack. For example:    Stack<Integer> stack = new Stack<>();     stack.push(10);     stack.push(20);     int topElement = stack.pop(); // Removes and returns the top element, 20 Stacks are used for managing function calls, evaluating expressions, and backtracking algorithms like depth-first search. Queues: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Elements are added (enqueued) at the rear and removed (dequeued) from the front. For example:    Queue<Integer> queue = new LinkedList<>();     queue.add(10); // Enqueue     queue.add(20);     int frontElement = queue.remove(); // Dequeue, returns 10 Queues are useful in scenarios like task scheduling, handling of asynchronous data (e.g., IO buffering), and breadth-first search algorithms. Non-linear Data Structures: Non-linear data structures do not organize elements in a sequential order; instead, they are arranged in a hierarchical manner. Common non-linear data structures include trees and graphs. Trees: A tree is a hierarchical structure consisting of nodes, with a root node and children node forming a parent-child relationship. Binary trees, binary search trees (BST), AVL trees, and heap trees are examples. For instance, a simple binary tree:    class TreeNode {        int data;        TreeNode left, right;          TreeNode(int d) {           data = d;           left = right = null;        }     }   

   TreeNode root = new TreeNode(10);     root.left = new TreeNode(5);     root.right = new TreeNode(15); Trees are utilized in databases, file systems, and network routing algorithms due to their hierarchical nature and efficient search, insert, and delete operations in balanced trees like AVL and red-black trees. Graphs: A graph is a collection of nodes (vertices) connected by edges. Graphs can be directed or undirected, weighted or unweighted. Graphs are represented using adjacency lists or adjacency matrices. For example, an adjacency list representation:    class Graph {        private int V; // Number of vertices        private LinkedList<Integer> adj[];          Graph(int v) {           V = v;           adj = new LinkedList[v];           for (int i = 0; i < v; ++i)              adj[i] = new LinkedList<>();        }          void addEdge(int v, int w) { adj[v].add(w); } // Add w to v’s list.     }       Graph g = new Graph(5);     g.addEdge(0, 1);     g.addEdge(0, 4);     g.addEdge(1, 2);     g.addEdge(1, 3);     g.addEdge(1, 4);     g.addEdge(2, 3);     g.addEdge(3, 4); Graphs are pivotal in networking, social networks, recommendation systems, and various optimization problems solved using algorithms like Dijkstra’s and Floyd-Warshall for shortest paths, and Prim’s and Kruskal’s for minimum spanning trees. Selecting the appropriate data structure depends on the specific requirements of the application, such as the efficiency of operations like access, insertion, deletion, and the complexity of implementation. Proficiency in understanding and implementing data structures lays the groundwork for developing efficient and optimized software solutions. 1.5 Types of Algorithms Algorithms can be classified in various ways based on their design paradigm, purpose, and implementation specifics. Understanding these classifications helps in choosing the appropriate algorithmic approach for solving a particular problem. Several key types of algorithms are widely recognized in computer science:

Divide and Conquer Dynamic Programming Greedy Algorithms Backtracking Branch and Bound Brute Force Randomized Algorithms Divide and Conquer algorithms work by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The most common examples of divide and conquer algorithms are merge sort and quicksort. void mergeSort(int arr[], int l, int r) {     if (l < r) {        int m = l + (r - l) / 2;        mergeSort(arr, l, m);        mergeSort(arr, m + 1, r);        merge(arr, l, m, r);     }  }    void merge(int arr[], int l, int m, int r) {     int n1 = m - l + 1;     int n2 = r - m;     int L[] = new int[n1];     int R[] = new int[n2];     for (int i = 0; i < n1; i++)        L[i] = arr[l + i];     for (int j = 0; j < n2; j++)        R[j] = arr[m + 1 + j];     int i = 0, j = 0;     int k = l;     while (i < n1 && j < n2) {        if (L[i] <= R[j]) {           arr[k] = L[i];           i++;        } else {           arr[k] = R[j];           j++;        }        k++;     }     while (i < n1) {        arr[k] = L[i];        i++;        k++;     }     while (j < n2) {        arr[k] = R[j];