{"id":692,"date":"2024-08-04T15:19:57","date_gmt":"2024-08-04T14:19:57","guid":{"rendered":"https:\/\/cyberenlightener.com\/?page_id=692"},"modified":"2024-11-26T12:16:05","modified_gmt":"2024-11-26T12:16:05","slug":"data-structures","status":"publish","type":"page","link":"https:\/\/cyberenlightener.com\/?page_id=692","title":{"rendered":"Introduction to Data Structure"},"content":{"rendered":"\n<h4 class=\"wp-block-heading\">Topics Covered<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong><a href=\"#Time\">Time Complexity, Asymptotic Notations,<\/a><\/strong><\/li>\n\n\n\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong><a href=\"#RecRel\">Solving Recurrence Relations <\/a><\/strong><\/li>\n\n\n\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong>Linear Data Structures Demystified: Arrays, <a href=\"#StackQ\">Stacks, Queues<\/a>, <\/strong><\/li>\n\n\n\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong>Conversion From Infix to Postfix\/Prefix: Practical Applications of Stacks in Expression Evaluation<\/strong><\/li>\n\n\n\n<li class=\"List\"><strong><a href=\"#List\">Linked List : Singly,Doubly and Circular<\/a><\/strong><\/li>\n\n\n\n<li><a href=\"#Poly\"><strong>Application of Linked List : Polynomial Representation and Addition<\/strong><\/a><\/li>\n\n\n\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong>Searching Techniques: <a href=\"#Linear\">Linear<\/a><\/strong> <strong> vs. <a href=\"#BinS\">Binary Search<\/a><\/strong> <\/li>\n\n\n\n<li class=\"wp-embed-aspect-16-9 wp-has-aspect-ratio\"><strong>Introduction  into Sorting Algorithms: Bubble Sort, Selection Sort , Insertion Sort,<a href=\"#Merge\">Merge Sort<\/a>,  <a href=\"#Counting\">Counting Sort<\/a>, <\/strong><a href=\"https:\/\/youtu.be\/ZtlOOq7q2Mk?si=NevTPVK98J9vPpAs\"><strong>Quick Sort<\/strong> <\/a><strong>&amp; <a href=\"https:\/\/youtu.be\/6SmxrKeYu3s?si=y5HuDFg5UW2-VgtL\">Heap<\/a>&amp;<a href=\"https:\/\/youtu.be\/RGn41bfI9YU?si=G_9K_1ZjmRM-jWyv\"> HeapSort<\/a><\/strong><\/li>\n\n\n\n<li><strong>Trees : Binary Tree, <a href=\"#BinSearchTree\">Binary Search Tree<\/a> (<a href=\"#kthsmall\">finding kth smallest element<\/a>)and Inorder, Pre-order and Post-Order Traversal in BST<\/strong><\/li>\n\n\n\n<li><strong>Special Tree: <a href=\"#AVL\">AVL Tree<\/a><\/strong> <a href=\"#AVLDEL\">(Deletion)<\/a><\/li>\n\n\n\n<li><strong><a href=\"#Hash\">Hashing<\/a><\/strong><\/li>\n\n\n\n<li><\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>Algorithms and data structures are the bedrock of computer science. They provide the methods and frameworks needed to process data efficiently, ensuring that software performs optimally under various conditions. An understanding of algorithms and data structures enables developers to create programs that are not only correct but also efficient and scalable.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fundamentals of Algorithm Analysis<\/h4>\n\n\n\n<p>Algorithm analysis is a critical aspect of understanding and designing algorithms. It involves evaluating the performance of an algorithm, focusing primarily on its space and time complexity. These metrics help in determining how well an algorithm will perform as the input size increases and how it will utilize system resources.<\/p>\n\n\n\n<p><strong>Space Complexity<\/strong><\/p>\n\n\n\n<p>Space complexity refers to the amount of memory an algorithm needs to execute. It is an important factor in environments where memory is limited or where large data sets are involved. Space complexity is often divided into two parts:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Fixed Part:<\/strong> This includes memory required by the algorithm that does not depend on the size of the input. For example, this could be the space needed for constants, static variables, and the program code itself.<\/li>\n\n\n\n<li><strong>Variable Part:<\/strong> This includes memory that depends on the size of the input. For example, if an algorithm needs to create an array of size <code>n<\/code> to store input data, the space complexity would increase linearly with <code>n<\/code>.<\/li>\n<\/ul>\n\n\n\n<p><em>Example:<\/em> a dynamic array to store <code>n<\/code> integers:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int* createArray(int n) {\n    int* arr = (int*)malloc(n * sizeof(int));  \/\/ Dynamic array of size n\n    return arr;\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Space Complexity:<\/strong> The space complexity of this algorithm is O(n) because it requires memory proportional to the size of the input <code>n<\/code>.<\/li>\n<\/ul>\n\n\n\n<p>Another example is an algorithm that uses a fixed amount of memory regardless of the input size:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int sum(int a, int b) {\n    return a + b;\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Space Complexity:<\/strong> The space complexity here is O(1) (constant space) since the memory requirement does not change with the size of the input.<\/li>\n<\/ul>\n\n\n\n<p id=\"Time\"><strong>Time Complexity<\/strong><\/p>\n\n\n\n<p>Time complexity measures the amount of time an algorithm takes to complete as a function of the input size. It provides a way to estimate the running time of an algorithm, which is crucial for understanding how it will scale as the input size grows.<\/p>\n\n\n\n<p>Time complexity is usually expressed using asymptotic notations, which provide a high-level understanding of the algorithm\u2019s performance.<\/p>\n\n\n\n<p><strong>Types of Asymptotic Notations<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Big O Notation (O):<\/strong> Big O notation describes the upper bound of the time complexity. It represents the worst-case scenario, providing the maximum time an algorithm will take to complete as the input size increases.<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Example:<\/em> For a simple linear search algorithm that searches for a value in an unsorted array of <code>n<\/code> elements, the time complexity is O(n) because, in the worst case, the algorithm may have to check every element in the array.<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>   int linearSearch(int arr&#91;], int n, int x) {\n       for (int i = 0; i &lt; n; i++) {\n           if (arr&#91;i] == x) {\n               return i;\n           }\n       }\n       return -1;\n   }<\/code><\/pre>\n\n\n\n<ul start=\"2\" class=\"wp-block-list\">\n<li><strong>Omega Notation (\u03a9):<\/strong> Omega notation describes the lower bound of the time complexity. It represents the best-case scenario, giving the minimum time an algorithm will take to complete.<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>Example:<\/em> For the linear search algorithm above, the best-case time complexity is \u03a9(1), which occurs if the desired element is the first element in the array.<\/li>\n<\/ul>\n\n\n\n<ul start=\"2\" class=\"wp-block-list\">\n<li><strong>Theta Notation (\u0398):<\/strong> Theta notation provides a tight bound on the time complexity, meaning it gives both the upper and lower bounds. When the best-case and worst-case time complexities are the same, we use Theta notation.<\/li>\n<\/ul>\n\n\n\n<p><strong>Orders of Growth<\/strong><\/p>\n\n\n\n<p>The efficiency of an algorithm is also understood through its order of growth, which is how the time or space complexity of an algorithm increases as the input size increases.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Constant Time \u2013 O(1):<\/strong> The algorithm&#8217;s performance is constant, and it does not depend on the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> Accessing a specific element in an array by index.<\/li>\n\n\n\n<li><strong>Logarithmic Time \u2013 O(log n):<\/strong> The time complexity increases logarithmically with the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> Binary search algorithm, which divides the search space in half with each step.<\/li>\n\n\n\n<li><strong>Linear Time \u2013 O(n):<\/strong> The time complexity increases linearly with the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> Linear search, where each element is checked one by one.<\/li>\n\n\n\n<li><strong>Linearithmic Time \u2013 O(n log n):<\/strong> The time complexity increases in proportion to n log n. This is common in efficient sorting algorithms.<\/li>\n\n\n\n<li><em>Example:<\/em> Merge sort or quicksort algorithms.<\/li>\n\n\n\n<li><strong>Quadratic Time \u2013 O(n\u00b2):<\/strong> The time complexity increases quadratically with the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> A simple bubble sort algorithm, where each element is compared with every other element.<\/li>\n\n\n\n<li><strong>Cubic Time \u2013 O(n\u00b3):<\/strong> The time complexity increases cubically with the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> Algorithms that involve three nested loops, such as matrix multiplication.<\/li>\n\n\n\n<li><strong>Exponential Time \u2013 O(2^n):<\/strong> The time complexity doubles with each additional element in the input.<\/li>\n\n\n\n<li><em>Example:<\/em> Algorithms that solve the traveling salesman problem through brute-force search.<\/li>\n\n\n\n<li><strong>Factorial Time \u2013 O(n!):<\/strong> The time complexity increases factorially with the input size.<\/li>\n\n\n\n<li><em>Example:<\/em> Algorithms that generate all possible permutations of a set.<\/li>\n<\/ul>\n\n\n\n<p><strong>Algorithm Efficiency: Best Case, Worst Case, Average Case<\/strong><\/p>\n\n\n\n<p>Understanding the best, worst, and average cases of an algorithm is essential for analyzing its performance in different scenarios.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Best Case:<\/strong> This is the scenario where the algorithm performs the minimum number of operations. It is the most favorable outcome.<\/li>\n\n\n\n<li><em>Example:<\/em> For a linear search, the best-case scenario occurs when the desired element is the first element in the array, giving a time complexity of O(1).<\/li>\n\n\n\n<li><strong>Worst Case:<\/strong> This scenario represents the maximum number of operations the algorithm could perform. It is the least favorable outcome.<\/li>\n\n\n\n<li><em>Example:<\/em> In the linear search algorithm, the worst-case occurs when the desired element is at the last position or not present at all, leading to a time complexity of O(n).<\/li>\n\n\n\n<li><strong>Average Case:<\/strong> The average case represents the expected performance of the algorithm under typical conditions, assuming all inputs are equally likely. It provides a more realistic measure of the algorithm\u2019s efficiency.<\/li>\n\n\n\n<li><em>Example:<\/em> For linear search, assuming the desired element is equally likely to be at any position in the array, the average time complexity would be O(n\/2), which simplifies to O(n).<\/li>\n<\/ul>\n\n\n\n<p><strong>Example: Binary Search Algorithm<\/strong><\/p>\n\n\n\n<p>To further illustrate these concepts, consider the binary search algorithm, which is used to find an element in a sorted array.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int binarySearch(int arr&#91;], int n, int x) {\n    int left = 0, right = n - 1;\n    while (left &lt;= right) {\n        int mid = left + (right - left) \/ 2;\n        if (arr&#91;mid] == x) {\n            return mid;  \/\/ Element found\n        }\n        if (arr&#91;mid] &lt; x) {\n            left = mid + 1;\n        } else {\n            right = mid - 1;\n        }\n    }\n    return -1;  \/\/ Element not found\n}<\/code><\/pre>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong><\/li>\n\n\n\n<li><strong>Best Case:<\/strong> O(1) \u2013 The element is found at the mid-point of the array in the first comparison.<\/li>\n\n\n\n<li><strong>Worst Case:<\/strong> O(log n) \u2013 The algorithm reduces the search space by half with each iteration, so the maximum number of comparisons is logarithmic in relation to the array size.<\/li>\n\n\n\n<li><strong>Average Case:<\/strong> O(log n) \u2013 On average, the element will be found after log n comparisons.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong> O(1) \u2013 The algorithm only requires a constant amount of additional memory, regardless of the input size.<\/li>\n<\/ul>\n\n\n\n<p>Understanding the importance of algorithms and data structures, along with the concepts of space and time complexity, is crucial for developing efficient software. Through careful analysis using asymptotic notations and understanding different scenarios (best, worst, and average cases), developers can create algorithms that perform optimally, even as the size of the input grows. This knowledge is foundational for tackling more complex problems in computer science and engineering, leading to better, faster, and more scalable solutions.<\/p>\n\n\n\n<p>Here\u2019s a comparison of best case, worst case, and average case in a tabular format:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th><strong>Case<\/strong><\/th><th><strong>Description<\/strong><\/th><th><strong>Purpose<\/strong><\/th><th><strong>Example: Linear Search<\/strong><\/th><th><strong>Example: Binary Search<\/strong><\/th><\/tr><\/thead><tbody><tr><td><strong>Best Case<\/strong><\/td><td>The scenario where the algorithm performs the minimum number of operations.<\/td><td>Provides an optimistic view of the algorithm\u2019s efficiency.<\/td><td>O(1): Desired element is the first in the array.<\/td><td>O(1): Desired element is at the middle.<\/td><\/tr><tr><td><strong>Worst Case<\/strong><\/td><td>The scenario where the algorithm performs the maximum number of operations.<\/td><td>Ensures the algorithm won&#8217;t exceed a particular performance threshold.<\/td><td>O(n): Desired element is the last or not present.<\/td><td>O(log n): Desired element is not in the array.<\/td><\/tr><tr><td><strong>Average Case<\/strong><\/td><td>The scenario representing the expected performance under typical conditions.<\/td><td>Offers a realistic estimate of the algorithm\u2019s performance.<\/td><td>O(n): On average, the desired element could be anywhere in the array.<\/td><td>O(log n): Expected number of operations needed to find the element.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>This above  table summarizes how each case reflects the algorithm\u2019s performance in different situations, using linear search and binary search as examples.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"RecRel\">Recurrence Relation<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"424\" height=\"466\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff11.png\" alt=\"\" class=\"wp-image-855\" style=\"width:941px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff11.png 424w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff11-273x300.png 273w\" sizes=\"auto, (max-width: 424px) 100vw, 424px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"600\" height=\"451\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff3.png\" alt=\"\" class=\"wp-image-856\" style=\"width:805px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff3.png 600w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff3-300x226.png 300w\" sizes=\"auto, (max-width: 600px) 100vw, 600px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"584\" height=\"441\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff4.png\" alt=\"\" class=\"wp-image-857\" style=\"width:891px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff4.png 584w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/ff4-300x227.png 300w\" sizes=\"auto, (max-width: 584px) 100vw, 584px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Summary<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Iteration Method (a):<\/strong> Involves expanding the recurrence and identifying patterns.<\/li>\n\n\n\n<li><strong>Substitution Method (b):<\/strong> Involves guessing the solution and proving it via induction.<\/li>\n\n\n\n<li><strong>Master Method (c):<\/strong> Provides a direct way to solve recurrences of the form ( T(n) = aT(n\/b) + f(n) ).<\/li>\n\n\n\n<li><strong>Recursive Tree Method (d):<\/strong> Visualizes the recurrence as a tree to sum the costs at each level.<\/li>\n<\/ul>\n\n\n\n<p>Each method has its own strengths and is suited to different types of recurrence relations. Understanding these methods provides a comprehensive toolkit for analyzing and solving recurrences in algorithmic problems.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Application of  Recursion : Tower of Hanoi<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"872\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-872x1024.jpg\" alt=\"\" class=\"wp-image-833\" style=\"width:446px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-872x1024.jpg 872w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-256x300.jpg 256w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-768x902.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-1308x1536.jpg 1308w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1.jpg 1363w\" sizes=\"auto, (max-width: 872px) 100vw, 872px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-768x1024.jpg\" alt=\"\" class=\"wp-image-835\" style=\"width:494px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-768x1024.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-225x300.jpg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1152x1536.jpg 1152w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2.jpg 1200w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"764\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3-764x1024.jpeg\" alt=\"\" class=\"wp-image-793\" style=\"width:513px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3-764x1024.jpeg 764w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3-224x300.jpeg 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3-768x1029.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3-1146x1536.jpeg 1146w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t3.jpeg 1194w\" sizes=\"auto, (max-width: 764px) 100vw, 764px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t4-768x1024.jpeg\" alt=\"\" class=\"wp-image-794\" style=\"width:526px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t4-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t4-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t4-1152x1536.jpeg 1152w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t4.jpeg 1200w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"777\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5-777x1024.jpeg\" alt=\"\" class=\"wp-image-795\" style=\"width:521px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5-777x1024.jpeg 777w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5-228x300.jpeg 228w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5-768x1012.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5-1165x1536.jpeg 1165w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/t5.jpeg 1214w\" sizes=\"auto, (max-width: 777px) 100vw, 777px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Time Complexity &amp; Asymptotic Notations <\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Lec-4-What is Big O?What is Big \u0398? What is  Big \u03a9 notation?|Notational class to present algo-time.\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/gmL4rJWrZKs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solving Recurrence Relation<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Lec-5 : Recurrences\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/RqMC5ObWQxY?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Lec 6: Master methods || Data Structures and Algorithms\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/zmyY4OxmFdA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Solving Recurrence Relation Using Master Method<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"888\" height=\"359\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/MASTER.png\" alt=\"\" class=\"wp-image-803\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/MASTER.png 888w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/MASTER-300x121.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/MASTER-768x310.png 768w\" sizes=\"auto, (max-width: 888px) 100vw, 888px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"813\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12-813x1024.jpeg\" alt=\"\" class=\"wp-image-807\" style=\"width:781px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12-813x1024.jpeg 813w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12-238x300.jpeg 238w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12-768x967.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12-1220x1536.jpeg 1220w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/12.jpeg 1271w\" sizes=\"auto, (max-width: 813px) 100vw, 813px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"824\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14-824x1024.png\" alt=\"\" class=\"wp-image-809\" style=\"width:794px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14-824x1024.png 824w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14-241x300.png 241w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14-768x954.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14-1236x1536.png 1236w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/14.png 1287w\" sizes=\"auto, (max-width: 824px) 100vw, 824px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\"><strong>Solving Recurrence Relation Using Recursion Tree<\/strong><\/h4>\n\n\n\n<h4 class=\"wp-block-heading\">Recursion Tree Method<\/h4>\n\n\n\n<p>Recursion is a fundamental technique in computer science and mathematics that enables a function to call itself repeatedly, breaking down complex problems into more manageable sub-problems. One of the most effective ways to analyze and understand recursive algorithms is through a visual tool known as a recursion tree. This article will explore the concept of recursion trees, their structure, their role in time complexity analysis, and practical examples of how they are used to evaluate recursive functions.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"599\" height=\"370\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-4.png\" alt=\"\" class=\"wp-image-780\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-4.png 599w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-4-300x185.png 300w\" sizes=\"auto, (max-width: 599px) 100vw, 599px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading\">What is a Recursion Tree?<\/h4>\n\n\n\n<p>A recursion tree is a diagrammatic representation that illustrates how a recursive function unfolds during its execution. It shows the different stages of recursive calls, how they branch out from one another, and how they eventually converge upon reaching the base case. By studying a recursion tree, one can gain a deeper understanding of the recursive process, its efficiency, and the computational resources it requires.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Structure of a Recursion Tree<\/h4>\n\n\n\n<p>In a recursion tree, each node represents a specific instance of a recursive call. The root node is the initial call to the function, while subsequent calls are represented as child nodes that branch out from the parent node. The number of branches emanating from a node is determined by the number of recursive calls made by the function at that stage. The depth of the tree reflects how many times the function recursively calls itself before reaching the base case.<\/p>\n\n\n\n<p><strong>Base Case:<\/strong><br>The base case is the condition that halts the recursion. In a recursion tree, the nodes corresponding to the base case are typically leaf nodes, meaning they do not lead to further recursive calls. These nodes mark the point at which the recursive process begins to reverse, with the function returning values up the tree.<\/p>\n\n\n\n<p><strong>Recursive Calls:<\/strong><br>Child nodes in the tree represent the recursive calls generated by the function. Each child node represents a smaller instance of the original problem, with different parameter values passed to the function. This recursive decomposition continues until all branches reach a base case.<\/p>\n\n\n\n<p>To comprehend how a recursive function operates, it is useful to trace the execution flow through a recursion tree. Starting at the root node, you follow the branches to see how the function calls itself repeatedly, breaking the problem down into smaller parts. As the base cases are reached, the recursion begins to unwind, with each level of the tree returning values that contribute to the final solution.<\/p>\n\n\n\n<p>Consider a recursive function that calculates the power of a number, for example:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def calculate_power(base, exponent):\n    if exponent == 0:\n        return 1\n    return base * calculate_power(base, exponent - 1)<\/code><\/pre>\n\n\n\n<p>For an input of <code>calculate_power(3, 4)<\/code>, the recursion tree would look like this:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>    calculate_power(3, 4)\n            |\n    3 * calculate_power(3, 3)\n            |\n    3 * calculate_power(3, 2)\n            |\n    3 * calculate_power(3, 1)\n            |\n    3 * calculate_power(3, 0)\n            |\n            1<\/code><\/pre>\n\n\n\n<p>This recursion tree demonstrates that each recursive call reduces the exponent by one until the base case <code>exponent == 0<\/code> is reached, at which point the recursion halts, and the values are returned up the tree.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Time Complexity Analysis Using Recursion Trees<\/h4>\n\n\n\n<p>Recursion trees are invaluable for analyzing the time complexity of recursive algorithms. By examining the tree\u2019s structure, we can determine the number of recursive calls made at each level and the amount of work done at each step. This analysis is crucial for understanding the overall efficiency of an algorithm and identifying areas for potential optimization.<\/p>\n\n\n\n<p><strong>Linear Recursion Example:<\/strong><br>Consider a function that calculates the sum of integers from <code>1<\/code> to <code>n<\/code>. The pseudo-code might look like this:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def sum_integers(n):\n    if n == 0:\n        return 0\n    return n + sum_integers(n - 1)<\/code><\/pre>\n\n\n\n<p>The recursion tree for <code>sum_integers(4)<\/code> would appear as follows:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>    sum_integers(4)\n            |\n    4 + sum_integers(3)\n            |\n    3 + sum_integers(2)\n            |\n    2 + sum_integers(1)\n            |\n    1 + sum_integers(0)\n            |\n            0<\/code><\/pre>\n\n\n\n<p>This is an example of <strong>linear recursion<\/strong>, where each function call leads to exactly one subsequent call. The time complexity is O(n), as the function makes <code>n<\/code> recursive calls.<\/p>\n\n\n\n<p><strong>Tree Recursion Example:<\/strong><br>Tree recursion occurs when a function makes multiple recursive calls within each execution. A classic example is the calculation of Fibonacci numbers. Here\u2019s a simplified version:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def fibonacci(n):\n    if n &lt;= 1:\n        return n\n    return fibonacci(n - 1) + fibonacci(n - 2)<\/code><\/pre>\n\n\n\n<p>The recursion tree for <code>fibonacci(4)<\/code> would look like this:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>            fibonacci(4)\n               \/    \\\n       fibonacci(3)  fibonacci(2)\n          \/   \\        \/   \\\n  fibonacci(2) fibonacci(1) fibonacci(1) fibonacci(0)\n     \/   \\\nfibonacci(1) fibonacci(0)<\/code><\/pre>\n\n\n\n<p>In this example, each recursive call generates two further calls, leading to an exponential growth in the number of calls. The time complexity for this tree recursion is O(2^n), which makes it less efficient for large inputs.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">The Recursion Tree Method in Depth<\/h4>\n\n\n\n<p>The recursion tree method is a powerful technique for solving recurrence relations that define the time complexity of recursive algorithms. Recurrence relations are mathematical expressions that describe the overall time required by a recursive algorithm in terms of the time required by smaller sub-problems.<\/p>\n\n\n\n<p><strong>Example:<\/strong><br>Consider the recurrence relation <code>T(n) = 2T(n\/2) + O(n)<\/code>, which might describe the time complexity of the Merge Sort algorithm. The recursion tree for this relation would help us understand that each level of the tree performs <code>O(n)<\/code> work, and the total height of the tree is <code>log n<\/code>, leading to an overall time complexity of <code>O(n log n)<\/code>.<\/p>\n\n\n\n<p>The binary search algorithm, on the other hand, is described by the recurrence relation <code>T(n) = T(n\/2) + O(1)<\/code>. The recursion tree for this relation shows that each level of the tree reduces the problem size by half, resulting in a logarithmic time complexity <code>O(log n)<\/code>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h4 class=\"wp-block-heading\">Practical Applications of Recursion Trees<\/h4>\n\n\n\n<p>Recursion trees are not just theoretical constructs; they have practical applications in analyzing and optimizing algorithms in various domains, including sorting, searching, and dynamic programming.<\/p>\n\n\n\n<p><strong>Sorting Algorithms:<\/strong><br>In sorting algorithms like Quick Sort and Merge Sort, recursion trees help visualize how the array is repeatedly divided into smaller sub-arrays and then merged or sorted. This visualization aids in understanding the time complexity and guiding optimization efforts.<\/p>\n\n\n\n<p><strong>Dynamic Programming:<\/strong><br>In dynamic programming, recursion trees help identify overlapping sub-problems, which can then be optimized using memoization or tabulation. This prevents the exponential growth of recursive calls and reduces the time complexity from exponential to polynomial.<\/p>\n\n\n\n<p><strong>Divide and Conquer:<\/strong><br>Recursion trees are integral to analyzing divide-and-conquer algorithms, where a problem is divided into smaller sub-problems, each solved recursively. Understanding the recursion tree helps determine how efficiently the problem is being divided and combined.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p>The recursion tree method is a valuable tool for understanding and analyzing recursive algorithms. By breaking down the execution of a recursive function into a tree structure, we can visualize its behavior, assess its time complexity, and optimize its performance. Whether dealing with simple linear recursion or more complex tree recursion, mastering the recursion tree method is essential for computer scientists, mathematicians, and anyone working with algorithms.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-768x1024.jpeg\" alt=\"\" class=\"wp-image-765\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-1.jpeg 960w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"774\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-2-774x1024.jpeg\" alt=\"\" class=\"wp-image-766\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-2-774x1024.jpeg 774w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-2-227x300.jpeg 227w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-2-768x1016.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-2.jpeg 968w\" sizes=\"auto, (max-width: 774px) 100vw, 774px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"764\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-2-764x1024.jpeg\" alt=\"\" class=\"wp-image-767\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-2-764x1024.jpeg 764w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-2-224x300.jpeg 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-2-768x1029.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-2.jpeg 955w\" sizes=\"auto, (max-width: 764px) 100vw, 764px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"766\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/4-1-766x1024.jpeg\" alt=\"\" class=\"wp-image-768\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/4-1-766x1024.jpeg 766w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/4-1-224x300.jpeg 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/4-1-768x1027.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/4-1.jpeg 957w\" sizes=\"auto, (max-width: 766px) 100vw, 766px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"754\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/5-1-754x1024.jpeg\" alt=\"\" class=\"wp-image-769\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/5-1-754x1024.jpeg 754w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/5-1-221x300.jpeg 221w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/5-1-768x1044.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/5-1.jpeg 942w\" sizes=\"auto, (max-width: 754px) 100vw, 754px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"766\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/6-1-766x1024.jpeg\" alt=\"\" class=\"wp-image-770\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/6-1-766x1024.jpeg 766w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/6-1-224x300.jpeg 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/6-1-768x1027.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/6-1.jpeg 957w\" sizes=\"auto, (max-width: 766px) 100vw, 766px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"779\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/7-1-779x1024.jpeg\" alt=\"\" class=\"wp-image-771\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/7-1-779x1024.jpeg 779w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/7-1-228x300.jpeg 228w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/7-1-768x1009.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/7-1.jpeg 974w\" sizes=\"auto, (max-width: 779px) 100vw, 779px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"StackQ\"><strong>Stacks and Queues <\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Lec 7 : Stack &amp; Queue\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/h61AxkOOpyk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">Stack Data Structure: Detailed Overview <\/h3>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"851\" height=\"470\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st1.png\" alt=\"\" class=\"wp-image-859\" style=\"width:671px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st1.png 851w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st1-300x166.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st1-768x424.png 768w\" sizes=\"auto, (max-width: 851px) 100vw, 851px\" \/><\/figure>\n\n\n\n<p>A stack is a fundamental data structure used extensively in computer science and programming. It operates on a Last In, First Out (LIFO) principle, meaning that the most recently added element is the first one to be removed. This characteristic makes stacks particularly useful in scenarios where the most recent data needs to be accessed first.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Stacks<\/h4>\n\n\n\n<p><strong>1. Basic Operations:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Push:<\/strong> This operation adds an element to the top of the stack. It is often implemented by incrementing the top index or adding a new node in the linked list-based implementation.<\/li>\n\n\n\n<li><strong>Pop:<\/strong> This operation removes the element from the top of the stack. It updates the top index or the head pointer of the linked list and returns the removed element.<\/li>\n\n\n\n<li><strong>Peek (or Top):<\/strong> This operation retrieves the element at the top of the stack without removing it. It allows access to the most recent element without altering the stack.<\/li>\n\n\n\n<li><strong>IsEmpty:<\/strong> This function checks if the stack is empty. It returns true if there are no elements in the stack and false otherwise.<\/li>\n<\/ul>\n\n\n\n<p><strong>2. Implementation:<\/strong><\/p>\n\n\n\n<p>Stacks can be implemented using arrays or linked lists. Each implementation has its own advantages and constraints.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Array-based Implementation:<\/strong> In this approach, a fixed-size array is used to represent the stack. The key component is an integer index, often called <code>top<\/code>, which keeps track of the index of the top element. The <code>push<\/code> operation increments this index and places the new element at that position, while the <code>pop<\/code> operation decrements the index. This method has a fixed capacity, making it essential to manage the stack size carefully to avoid overflow. <img decoding=\"async\" style=\"\" src=\"https:\/\/i.imgur.com\/2B02xyX.png\" alt=\"Array-based Stack\"><br><\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"785\" height=\"477\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st2.png\" alt=\"\" class=\"wp-image-860\" style=\"width:705px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st2.png 785w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st2-300x182.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/st2-768x467.png 768w\" sizes=\"auto, (max-width: 785px) 100vw, 785px\" \/><\/figure>\n\n\n\n<p><strong>3. Applications:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Expression Evaluation:<\/strong> Stacks are used to evaluate expressions, particularly in postfix (Reverse Polish Notation) and infix notations. For instance, converting infix expressions to postfix or evaluating postfix expressions involves using stacks to manage operators and operands.<\/li>\n\n\n\n<li><strong>Backtracking:<\/strong> Algorithms that require backtracking, such as depth-first search (DFS), use stacks to remember the path taken. Stacks help revert to the previous state by popping elements off the stack, enabling the exploration of alternative paths.<\/li>\n\n\n\n<li><strong>Function Call Management:<\/strong> The call stack manages function calls and local variables in programming languages. It tracks the order of function calls and supports recursion by storing return addresses and local variables for each call.<\/li>\n<\/ul>\n\n\n\n<p><strong>4. Performance Considerations:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong> Stack operations, including push, pop, and peek, operate in O(1) time. This constant time complexity is due to the direct access and modification of the top element.<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong> The space complexity is O(n), where <code>n<\/code> is the number of elements in the stack. Both array-based and linked list-based implementations require space proportional to the number of elements stored.<\/li>\n<\/ul>\n\n\n\n<p><strong>5. Common Pitfalls:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Overflow and Underflow:<\/strong><\/li>\n\n\n\n<li><strong>Overflow:<\/strong> In array-based stacks, pushing an element onto a full stack results in overflow. Proper checks and resizing strategies are required to manage capacity.<\/li>\n\n\n\n<li><strong>Underflow:<\/strong> Popping an element from an empty stack leads to underflow. Implementing checks to ensure the stack is not empty before popping is crucial.<\/li>\n<\/ul>\n\n\n\n<p><strong>6. Practical Examples:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Undo Mechanism in Applications:<\/strong> Many software applications implement undo functionality using stacks. Each action is pushed onto the stack, and undoing an action involves popping the most recent action and reversing it.<\/li>\n\n\n\n<li><strong>Balanced Parentheses Checking:<\/strong> Stacks are used to check for balanced parentheses in expressions or code snippets. Each opening parenthesis is pushed onto the stack, and each closing parenthesis triggers a pop operation, ensuring all parentheses are correctly matched.<\/li>\n<\/ul>\n\n\n\n<p>By understanding and utilizing stacks effectively, you can solve a variety of computational problems efficiently. Stacks provide a robust method for managing data with a LIFO ordering, making them an essential component of many algorithms and systems.<\/p>\n\n\n\n<p><strong><em>A sample C code for Stack:<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h&gt;\n#define MAX 100 \/\/ Define the maximum size of the stack\n\n\/\/ Structure to represent a stack\ntypedef struct {\n    int top; \/\/ Index of the top element\n    int arr&#91;MAX]; \/\/ Array to hold stack elements\n} Stack;\n\n\/\/ Function to initialize the stack\nvoid initialize(Stack *s) {\n    s-&gt;top = -1; \/\/ Set top to -1 indicating the stack is empty\n}\n\n\/\/ Function to check if the stack is empty\nint isEmpty(Stack *s) {\n    return s-&gt;top == -1;\n}\n\n\/\/ Function to check if the stack is full\nint isFull(Stack *s) {\n    return s-&gt;top == MAX - 1; \/\/ Use - instead of an incorrect dash symbol\n}\n\n\/\/ Function to add an element to the stack\nvoid push(Stack *s, int value) {\n    if (isFull(s)) {\n        printf(\"Stack overflow. Cannot push %d\\n\", value);\n        return;\n    }\n    s-&gt;arr&#91;++(s-&gt;top)] = value; \/\/ Increment top and add the element\n    printf(\"%d pushed to stack\\n\", value);\n}\n\n\/\/ Function to remove an element from the stack\nint pop(Stack *s) {\n    if (isEmpty(s)) {\n        printf(\"Stack underflow. Cannot pop\\n\");\n        return -1; \/\/ Return a sentinel value to indicate failure\n    }\n    return s-&gt;arr&#91;(s-&gt;top)--]; \/\/ Return the top element and decrement top\n}\n\n\/\/ Function to get the top element of the stack without removing it\nint peek(Stack *s) {\n    if (isEmpty(s)) {\n        printf(\"Stack is empty\\n\");\n        return -1; \/\/ Return a sentinel value to indicate failure\n    }\n    return s-&gt;arr&#91;s-&gt;top]; \/\/ Return the top element\n}\n\n\/\/ Function to display the elements of the stack\nvoid display(Stack *s) {\n    if (isEmpty(s)) {\n        printf(\"Stack is empty\\n\");\n        return;\n    }\n    printf(\"Stack elements are:\\n\");\n    for (int i = s-&gt;top; i &gt;= 0; i--) { \/\/ Use -- instead of an incorrect dash symbol\n        printf(\"%d\\n\", s-&gt;arr&#91;i]);\n    }\n}\n\n\/\/ Main function to demonstrate stack operations\nint main() {\n    Stack s;\n    initialize(&amp;s); \/\/ Initialize the stack\n\n    \/\/ Demonstrate stack operations\n    push(&amp;s, 10);\n    push(&amp;s, 20);\n    push(&amp;s, 30);\n    display(&amp;s);\n\n    printf(\"%d popped from stack\\n\", pop(&amp;s));\n    display(&amp;s);\n\n    printf(\"Top element is %d\\n\", peek(&amp;s));\n\n    return 0;\n}\n\n\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Queue and Circular Queue: Detailed Explanation<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">1. Linear <strong>Queue<\/strong><\/h4>\n\n\n\n<p><strong>Definition:<\/strong><br>A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed.<\/p>\n\n\n\n<p><strong>Operations:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Enqueue:<\/strong> Adds an element to the rear of the queue.<\/li>\n\n\n\n<li><strong>Dequeue:<\/strong> Removes an element from the front of the queue.<\/li>\n\n\n\n<li><strong>Front (Peek):<\/strong> Retrieves the element at the front of the queue without removing it.<\/li>\n\n\n\n<li><strong>IsEmpty:<\/strong> Checks whether the queue is empty.<\/li>\n\n\n\n<li><strong>IsFull:<\/strong> Checks whether the queue is full (for array-based implementation).<\/li>\n<\/ul>\n\n\n\n<p><strong>Applications:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Task Scheduling:<\/strong> Manages tasks in the order they arrive, such as print jobs or CPU task scheduling.<\/li>\n\n\n\n<li><strong>Data Buffers:<\/strong> Manages data streams where the order of processing is crucial.<\/li>\n\n\n\n<li><strong>Breadth-First Search (BFS):<\/strong> Used in BFS algorithms to explore nodes level by level.<\/li>\n<\/ul>\n\n\n\n<p><strong>Array-Based Implementation:<\/strong><\/p>\n\n\n\n<p><strong>Diagram:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Queue:\nFront -&gt; | 1 | &lt;- Front (first element to be removed)\n         | 2 |\n         | 3 |\n         | 4 | &lt;- Rear (most recent element added)<\/code><\/pre>\n\n\n\n<p><strong>Code Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\n#define MAX 100 \/\/ Maximum size of the queue\n\ntypedef struct {\n    int front, rear, size;\n    int arr&#91;MAX];\n} Queue;\n\n\/\/ Initialize the queue\nvoid initialize(Queue *q) {\n    q-&gt;front = 0;\n    q-&gt;rear = -1;\n    q-&gt;size = 0;\n}\n\n\/\/ Check if the queue is empty\nint isEmpty(Queue *q) {\n    return q-&gt;size == 0;\n}\n\n\/\/ Check if the queue is full\nint isFull(Queue *q) {\n    return q-&gt;size == MAX;\n}\n\n\/\/ Add an element to the queue\nvoid enqueue(Queue *q, int value) {\n    if (isFull(q)) {\n        printf(\"Queue is full. Cannot enqueue %d\\n\", value);\n        return;\n    }\n    q-&gt;rear =<\/code><\/pre>\n\n\n\n<p>2.Circular Queue<br><br>**Definition:**<br>A circular queue is a variation of the standard queue where the end of the queue wraps around to the beginning, effectively making the queue circular. This implementation overcomes the limitations of a linear array-based queue where elements may leave gaps.<br><br>**Operations:**<br>&#8211; Enqueue: Adds an element to the rear of the queue.<br>&#8211; Dequeue: Removes an element from the front of the queue.<br>&#8211; Front (Peek): Retrieves the element at the front without removing it.<br>&#8211; IsEmpty: Checks if the queue is empty.<br>&#8211; IsFull: Checks if the queue is full.<br><br><\/p>\n\n\n\n<p>Circular Queue (Max Size: 5):<br>Front -&gt; | 1 | &lt;- Front (first element to be removed)<br>| 2 |<br>| 3 |<br>| 4 |<br>| 5 | &lt;- Rear (most recent element added)<\/p>\n\n\n\n<p>After enqueue operations, the queue wraps around:<br>Front -&gt; | 6 |<br>| 7 |<br>| 8 |<br>| 9 |<br>| 10| &lt;- Rear<br><\/p>\n\n\n\n<h5 class=\"wp-block-heading\"><strong>Circular Queue<\/strong><\/h5>\n\n\n\n<p>Here is a complete C code implementation for a circular queue. This implementation uses an array to store the elements and maintains the <code>front<\/code>, <code>rear<\/code>, and <code>size<\/code> to manage the queue operations.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\n#define MAX 5 \/\/ Define the maximum size of the circular queue\n\ntypedef struct {\n    int front, rear, size;\n    int arr&#91;MAX];\n} CircularQueue;\n\n\/\/ Initialize the circular queue\nvoid initialize(CircularQueue *q) {\n    q-&gt;front = 0;\n    q-&gt;rear = -1;\n    q-&gt;size = 0;\n}\n\n\/\/ Check if the circular queue is empty\nint isEmpty(CircularQueue *q) {\n    return q-&gt;size == 0;\n}\n\n\/\/ Check if the circular queue is full\nint isFull(CircularQueue *q) {\n    return q-&gt;size == MAX;\n}\n\n\/\/ Add an element to the circular queue\nvoid enqueue(CircularQueue *q, int value) {\n    if (isFull(q)) {\n        printf(\"Queue is full. Cannot enqueue %d\\n\", value);\n        return;\n    }\n    q-&gt;rear = (q-&gt;rear + 1) % MAX; \/\/ Update rear index circularly\n    q-&gt;arr&#91;q-&gt;rear] = value;\n    q-&gt;size++;\n    printf(\"%d enqueued to queue\\n\", value);\n}\n\n\/\/ Remove an element from the circular queue\nint dequeue(CircularQueue *q) {\n    if (isEmpty(q)) {\n        printf(\"Queue is empty. Cannot dequeue\\n\");\n        return -1; \/\/ Sentinel value indicating error\n    }\n    int value = q-&gt;arr&#91;q-&gt;front];\n    q-&gt;front = (q-&gt;front + 1) % MAX; \/\/ Update front index circularly\n    q-&gt;size--;\n    return value;\n}\n\n\/\/ Retrieve the front element without removing it\nint front(CircularQueue *q) {\n    if (isEmpty(q)) {\n        printf(\"Queue is empty\\n\");\n        return -1; \/\/ Sentinel value indicating error\n    }\n    return q-&gt;arr&#91;q-&gt;front];\n}\n\n\/\/ Display the elements of the circular queue\nvoid display(CircularQueue *q) {\n    if (isEmpty(q)) {\n        printf(\"Queue is empty\\n\");\n        return;\n    }\n    printf(\"Queue elements are:\\n\");\n    for (int i = 0; i &lt; q-&gt;size; i++) {\n        printf(\"%d\\n\", q-&gt;arr&#91;(q-&gt;front + i) % MAX]);\n    }\n}\n\n\/\/ Main function to demonstrate circular queue operations\nint main() {\n    CircularQueue q;\n    initialize(&amp;q);\n\n    enqueue(&amp;q, 10);\n    enqueue(&amp;q, 20);\n    enqueue(&amp;q, 30);\n    enqueue(&amp;q, 40);\n    enqueue(&amp;q, 50);\n    display(&amp;q);\n\n    printf(\"%d dequeued from queue\\n\", dequeue(&amp;q));\n    printf(\"%d dequeued from queue\\n\", dequeue(&amp;q));\n    display(&amp;q);\n\n    enqueue(&amp;q, 60);\n    enqueue(&amp;q, 70);\n    display(&amp;q);\n\n    printf(\"Front element is %d\\n\", front(&amp;q));\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Explanation:<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Structure Definition:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>CircularQueue<\/code> structure contains:\n<ul class=\"wp-block-list\">\n<li><code>front<\/code>: Index of the first element.<\/li>\n\n\n\n<li><code>rear<\/code>: Index of the last element.<\/li>\n\n\n\n<li><code>size<\/code>: Number of elements in the queue.<\/li>\n\n\n\n<li><code>arr[MAX]<\/code>: Array to store the elements.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>initialize()<\/code> sets <code>front<\/code> to 0, <code>rear<\/code> to -1, and <code>size<\/code> to 0.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Check Functions:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>isEmpty()<\/code> returns true if the queue has no elements.<\/li>\n\n\n\n<li><code>isFull()<\/code> returns true if the queue is full.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Enqueue Operation:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>enqueue()<\/code> adds an element to the rear of the queue. The <code>rear<\/code> index is updated circularly using modulo arithmetic.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Dequeue Operation:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>dequeue()<\/code> removes an element from the front of the queue. The <code>front<\/code> index is updated circularly using modulo arithmetic.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Front Operation:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>front()<\/code> retrieves the front element without removing it.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Display Function:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>display()<\/code> prints all elements from the front to the rear in the circular queue.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Main Function:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Demonstrates operations by enqueuing and dequeuing elements, and displaying the queue&#8217;s contents.<\/li>\n<\/ul>\n\n\n\n<p>This implementation ensures that the circular queue efficiently manages the elements, utilizing the available space effectively.<\/p>\n\n\n\n<h5 class=\"wp-block-heading\"><br><strong>Summary of Stack data structure.<\/strong><\/h5>\n\n\n\n<p><strong>Origin<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Introduced by Alan M. Turing in 1946 using the terms &#8220;bury&#8221; and &#8220;unbury&#8221; for subroutines<\/li>\n\n\n\n<li>Formally proposed by Klaus Samelson and Friedrich L. Bauer in 1955; patent filed in 1957<\/li>\n\n\n\n<li>Bauer received the IEEE Computer Pioneer Award in 1988 for the stack principle<\/li>\n<\/ul>\n\n\n\n<p><strong>Key Characteristics<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>LIFO (Last-In-First-Out) data structure<\/strong><\/li>\n\n\n\n<li><strong>Push<\/strong>: Adding an item to the stack<\/li>\n\n\n\n<li><strong>Pop<\/strong>: Removing an item from the stack<\/li>\n\n\n\n<li>Access is only at the top<\/li>\n<\/ul>\n\n\n\n<p><strong>Applications<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Conversion of Infix to Postfix or Prefix expressions<\/li>\n\n\n\n<li>Backtracking techniques<\/li>\n\n\n\n<li>Function call and return processes<\/li>\n\n\n\n<li>Saving local variables during nested function calls<\/li>\n\n\n\n<li>Web browser page-visited history<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\"><strong>Summary of QUEUE and Circular Queue<\/strong><\/h5>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/que_revised.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of queuue.\"><\/object><a id=\"wp-block-file--media-57f437d3-bc0a-4f90-82e0-c8c34fb06614\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/que_revised.pdf\">queuue<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/que_revised.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-57f437d3-bc0a-4f90-82e0-c8c34fb06614\">Download<\/a><\/div>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"842\" height=\"486\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/GATEWA.png\" alt=\"\" class=\"wp-image-908\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/GATEWA.png 842w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/GATEWA-300x173.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/GATEWA-768x443.png 768w\" sizes=\"auto, (max-width: 842px) 100vw, 842px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1024x720.jpeg\" alt=\"\" class=\"wp-image-909\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1024x720.jpeg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-300x211.jpeg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-768x540.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45.jpeg 1484w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"758\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1-758x1024.jpeg\" alt=\"\" class=\"wp-image-910\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1-758x1024.jpeg 758w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1-222x300.jpeg 222w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1-768x1038.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1-1137x1536.jpeg 1137w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.45-1.jpeg 1184w\" sizes=\"auto, (max-width: 758px) 100vw, 758px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.46-768x1024.jpeg\" alt=\"\" class=\"wp-image-911\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.46-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.46-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.46-1152x1536.jpeg 1152w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.07.46.jpeg 1200w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\">Understanding Expression Notations: Infix, Prefix, and Postfix<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">What are Expression Notations?<\/h3>\n\n\n\n<p>Expression notations are different ways to represent mathematical operations. These notations determine the placement of operators relative to their operands.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Infix Notation<\/h3>\n\n\n\n<p>In infix notation, the operator is positioned between its operands. This is the most commonly used format in everyday arithmetic.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Example:<\/strong> 2 + 3<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Postfix Notation<\/h3>\n\n\n\n<p>Postfix notation, also known as Reverse Polish Notation (RPN), places the operator after its operands.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Example:<\/strong> 2 3 +<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Prefix Notation<\/h3>\n\n\n\n<p>Prefix notation, or Polish Notation, positions the operator before its operands.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Example:<\/strong> + 2 3<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Evaluating Expressions<\/h3>\n\n\n\n<p>The method for evaluating each notation differs.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Infix:<\/strong> Requires considering operator precedence and parentheses to determine the order of operations.<\/li>\n\n\n\n<li><strong>Postfix:<\/strong> Typically involves using a stack data structure to process the expression from left to right.<\/li>\n\n\n\n<li><strong>Prefix:<\/strong> Similar to postfix, but evaluation proceeds from right to left using a stack.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Advantages and Disadvantages<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Infix:<\/strong> Easy to read for humans but can be complex for computers to process.<\/li>\n\n\n\n<li><strong>Postfix and Prefix:<\/strong> Often more efficient for computer processing as they eliminate the need for parentheses and complex precedence rules. However, they can be less intuitive for humans to understand.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"504\" height=\"290\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/COMPARISON.png\" alt=\"\" class=\"wp-image-693\" style=\"width:1199px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/COMPARISON.png 504w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/COMPARISON-300x173.png 300w\" sizes=\"auto, (max-width: 504px) 100vw, 504px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Conversion and Efficiency<\/h3>\n\n\n\n<p>It&#8217;s possible to convert between different notations. For example, infix expressions can be transformed into postfix or prefix form using algorithms like the Shunting Yard algorithm. Postfix and prefix notations generally offer performance advantages in computer applications due to their simpler evaluation process.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Choosing the Right Notation<\/h3>\n\n\n\n<p>The optimal notation depends on the specific application. Infix is preferred for human interaction, while postfix and prefix are often used in programming and compiler design for efficient expression handling.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Infix to Postfix Conversion<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"766\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/Postfix_Roy1-766x1024.jpeg\" alt=\"\" class=\"wp-image-729\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/Postfix_Roy1-766x1024.jpeg 766w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/Postfix_Roy1-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/Postfix_Roy1-768x1026.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/Postfix_Roy1.jpeg 958w\" sizes=\"auto, (max-width: 766px) 100vw, 766px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"773\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1-773x1024.jpeg\" alt=\"\" class=\"wp-image-730\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1-773x1024.jpeg 773w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1-226x300.jpeg 226w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1-768x1018.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/2-1.jpeg 966w\" sizes=\"auto, (max-width: 773px) 100vw, 773px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"772\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-1-772x1024.jpeg\" alt=\"\" class=\"wp-image-731\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-1-772x1024.jpeg 772w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-1-226x300.jpeg 226w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-1-768x1019.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/3-1.jpeg 965w\" sizes=\"auto, (max-width: 772px) 100vw, 772px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Infix to prefix conversion<\/strong><\/h2>\n\n\n\n<p>To transform an infix expression into a prefix expression, you can follow these steps using a stack data structure:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Reverse the Infix Expression<\/strong>: Start by reversing the original infix expression. As you reverse, swap every opening parenthesis <code>(<\/code> with a closing parenthesis <code>)<\/code> and vice versa.<\/li>\n\n\n\n<li><strong>Convert the Reversed Infix to a &#8220;Near-Postfix&#8221; Expression<\/strong>: Next, process the reversed infix expression to obtain a postfix expression. However, when you handle operators during this conversion, only pop operators from the stack if they have strictly greater precedence than the current operator (rather than popping for equal or greater precedence).<\/li>\n\n\n\n<li><strong>Reverse the Resulting Expression<\/strong>: Finally, take the postfix expression generated in the previous step and reverse it to obtain the desired prefix expression.<\/li>\n<\/ol>\n\n\n\n<p>Throughout the process, the stack is utilized to facilitate the conversion from infix to postfix, which is then adjusted to generate the prefix form.<\/p>\n\n\n\n<p>Let&#8217;s go through the process of converting the infix expression <code>(A + B) * (C - D)<\/code> to prefix notation, showing the stack at each step.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Step 1: Reverse the Infix Expression<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Original infix: <code>(A + B) * (C - D)<\/code><\/li>\n\n\n\n<li>Reversed expression: <code>(D - C) * (B + A)<\/code><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Step 2: Replace Each Parenthesis<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Replace <code>(<\/code> with <code>)<\/code> and vice versa in the reversed expression.<\/li>\n\n\n\n<li>After replacement: <code>)D - C( * )B + A(<\/code><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Step 3: Convert the Modified Expression to Postfix<\/h3>\n\n\n\n<p>Now we&#8217;ll convert <code>)D - C( * )B + A(<\/code> to postfix notation, showing the stack at each step.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>)<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>)<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>:<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>D<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>)<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>D<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>-<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>) -<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>D<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>C<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>) -<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>(<\/code><\/strong> (pop until <code>)<\/code>):<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Pop <code>-<\/code> and add to postfix.<\/li>\n\n\n\n<li><strong>Stack<\/strong>:<\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>*<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>*<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>)<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>* )<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>B<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>* )<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-B<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>+<\/code><\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>* ) +<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-B<\/code><\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Scan <code>A<\/code><\/strong>:\n<ul class=\"wp-block-list\">\n<li><strong>Stack<\/strong>: <code>* ) +<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-BA<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Scan <code>(<\/code><\/strong> (pop until <code>)<\/code>):\n<ul class=\"wp-block-list\">\n<li>Pop <code>+<\/code> and add to postfix.<\/li>\n\n\n\n<li><strong>Stack<\/strong>: <code>*<\/code><\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-BA+<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Pop remaining operators<\/strong>:\n<ul class=\"wp-block-list\">\n<li>Pop <code>*<\/code> and add to postfix.<\/li>\n\n\n\n<li><strong>Stack<\/strong>:<\/li>\n\n\n\n<li><strong>Postfix Expression<\/strong>: <code>DC-BA+*<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Step 4: Reverse the Postfix Expression<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Reverse the postfix expression <code>DC-BA+*<\/code> to obtain the prefix expression.<\/li>\n\n\n\n<li>Reversed postfix: <code>*+AB-CD<\/code><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Final Prefix Expression<\/h3>\n\n\n\n<p>The final prefix expression for the given infix expression <code>(A + B) * (C - D)<\/code> is <code>*+AB-CD<\/code>.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"799\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28-799x1024.jpeg\" alt=\"\" class=\"wp-image-906\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28-799x1024.jpeg 799w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28-234x300.jpeg 234w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28-768x985.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28-1198x1536.jpeg 1198w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-02-at-14.09.28.jpeg 1248w\" sizes=\"auto, (max-width: 799px) 100vw, 799px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong> Search Techniques<\/strong><\/h2>\n\n\n\n<p>Search algorithms are fundamental in computer science for locating specific data within a collection. There are various search algorithms, each with different efficiencies depending on the data structure and size. Two common search methods are <strong>linear search<\/strong> and <strong>binary search<\/strong>.<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Linear Search<\/strong>:\n<ul class=\"wp-block-list\">\n<li><strong>Description<\/strong>: Linear search is the simplest search algorithm. It checks each element in the array until the target value is found or the array ends. It&#8217;s effective for small or unsorted datasets.<\/li>\n\n\n\n<li><strong>Time Complexity<\/strong>: O(n), where n is the number of elements in the array.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Binary Search<\/strong>:\n<ul class=\"wp-block-list\">\n<li><strong>Description<\/strong>: Binary search is more efficient but requires the array to be sorted. It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half, otherwise in the right half.<\/li>\n\n\n\n<li><strong>Time Complexity<\/strong>: O(log n), making it significantly faster for large, sorted datasets.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>Here&#8217;s a simple C program implementing the linear search algorithm:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h&gt;\n\n\/\/ Function to perform linear search\nint linearSearch(int arr&#91;], int n, int target) {\n    for (int i = 0; i &lt; n; i++) {\n        if (arr&#91;i] == target) {\n            return i; \/\/ Return the index of the target element\n        }\n    }\n    return -1; \/\/ Return -1 if the element is not found\n}\n\nint main() {\n    int arr&#91;] = {10, 25, 30, 45, 60, 75};\n    int n = sizeof(arr) \/ sizeof(arr&#91;0]);\n    int target = 45;\n\n    int result = linearSearch(arr, n, target);\n\n    if (result != -1) {\n        printf(\"Element found at index %d\\n\", result);\n    } else {\n        printf(\"Element not found in the array\\n\");\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Explanation:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong><code>linearSearch<\/code> Function<\/strong>: Iterates through each element of the array to find the target value. If the target is found, the function returns the index; otherwise, it returns <code>-1<\/code>.<\/li>\n\n\n\n<li><strong><code>main<\/code> Function<\/strong>: Initializes an array and the target value to search for. It then calls <code>linearSearch<\/code> and prints the result.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Output:<\/h3>\n\n\n\n<p>If the target value <code>45<\/code> is in the array, the program will output:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Element found at index 3<\/code><\/pre>\n\n\n\n<p>If the target value is not in the array, it will output:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Element not found in the array\n\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"List\">Linked List<\/h2>\n\n\n\n<p class=\"has-text-align-center\"><\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Introduction to Singly linked list\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/HjHKOPyX1oc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube io wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Mastering Singly Linked Lists in C: Implementation, Operations, and Best Practices\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/iaImk4P5GsA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Doubly Linked List :  Hands on C programming for inserting a node at the beginning Data Structures\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/TMvt9CPAlxM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\">Applications of Linked List : Polynomial Representation &amp; Addition<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full\" id=\"Poly\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"720\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY.png\" alt=\"\" class=\"wp-image-1268\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY.png 960w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY-300x225.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY-768x576.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of POLY.\"><\/object><a id=\"wp-block-file--media-61f525e2-9e92-4776-8969-c21b6133d16d\" href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY.pdf\">POLY<\/a><a href=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/POLY.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-61f525e2-9e92-4776-8969-c21b6133d16d\">Download<\/a><\/div>\n\n\n\n<p id=\"Poly\"><\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Polynomials representation and addition using Linked List|| Basic Intro\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/tm_T_yZAjXo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"Linear\">Linear Search<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Linear Search: <\/strong><\/h3>\n\n\n\n<p><strong>Linear Search<\/strong> is a straightforward search algorithm that traverses each element of a list or array sequentially to locate a target value. It works by comparing the target with each element in the array one by one until the target is found or all elements are checked.<\/p>\n\n\n\n<p><strong>Key Characteristics:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Unsorted Data<\/strong>: It can search in both sorted and unsorted data.<\/li>\n\n\n\n<li><strong>Simplicity<\/strong>: Easy to implement and understand.<\/li>\n\n\n\n<li><strong>Time Complexity<\/strong>:<\/li>\n\n\n\n<li><strong>Best Case<\/strong>: ( O(1) ) \u2014 target is found at the first position.<\/li>\n\n\n\n<li><strong>Worst Case<\/strong>: ( O(n) ) \u2014 target is either absent or at the last position.<\/li>\n\n\n\n<li><strong>Space Complexity<\/strong>: ( O(1) ) \u2014 constant space is used.<\/li>\n<\/ul>\n\n\n\n<p><strong>Example<\/strong>:<\/p>\n\n\n\n<p>Let\u2019s search for the target value <code>56<\/code> in the following array:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Array: &#91;12, 34, 56, 78, 90]\nTarget: 56<\/code><\/pre>\n\n\n\n<p><strong>Steps<\/strong>:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Compare target (56) with the first element (12) \u2192 Not found.<\/li>\n\n\n\n<li>Compare target (56) with the second element (34) \u2192 Not found.<\/li>\n\n\n\n<li>Compare target (56) with the third element (56) \u2192 Found at index 2.<\/li>\n<\/ol>\n\n\n\n<p><strong>Explanation<\/strong>: Linear search checks each element until it finds the target <code>56<\/code> at index <code>2<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"BinS\"><strong>Binary Search<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"772\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch-772x1024.jpeg\" alt=\"\" class=\"wp-image-798\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch-772x1024.jpeg 772w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch-226x300.jpeg 226w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch-768x1019.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch-1158x1536.jpeg 1158w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/binsearch.jpeg 1206w\" sizes=\"auto, (max-width: 772px) 100vw, 772px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Selection Sort<\/strong><\/h2>\n\n\n\n<p>In computer science, selection sort is an <strong>in-place<\/strong> comparison sorting algorithm. <strong>It has an O(n<sup>2<\/sup>)<\/strong> time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort.<\/p>\n\n\n\n<p><strong>Selection sort<\/strong> is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited. The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. <\/p>\n\n\n\n<p>Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, <strong>exchanging (swapping<\/strong>) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.<\/p>\n\n\n\n<p>The time efficiency of selection sort is quadratic, so there are a number of sorting techniques which have better time complexity than selection sort.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"807\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-807x1024.jpg\" alt=\"\" class=\"wp-image-800\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-807x1024.jpg 807w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-236x300.jpg 236w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1-768x974.jpg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/1.jpg 1009w\" sizes=\"auto, (max-width: 807px) 100vw, 807px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"782\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/WhatsApp-Image-2024-08-12-at-4.51.33-PM-782x1024.jpeg\" alt=\"\" class=\"wp-image-723\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/WhatsApp-Image-2024-08-12-at-4.51.33-PM-782x1024.jpeg 782w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/WhatsApp-Image-2024-08-12-at-4.51.33-PM-229x300.jpeg 229w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/WhatsApp-Image-2024-08-12-at-4.51.33-PM-768x1005.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/08\/WhatsApp-Image-2024-08-12-at-4.51.33-PM.jpeg 978w\" sizes=\"auto, (max-width: 782px) 100vw, 782px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Steps of Selection Sort<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>i = 0<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start with the first element <code>64<\/code> as the current minimum.<\/li>\n\n\n\n<li>Compare with elements:\n<ul class=\"wp-block-list\">\n<li><code>j = 1<\/code>: Compare <code>64<\/code> with <code>25<\/code>, <code>25<\/code> is smaller.<\/li>\n\n\n\n<li><code>j = 2<\/code>: Compare <code>25<\/code> with <code>12<\/code>, <code>12<\/code> is smaller.<\/li>\n\n\n\n<li><code>j = 3<\/code>: Compare <code>12<\/code> with <code>22<\/code>, <code>12<\/code> remains smaller.<\/li>\n\n\n\n<li><code>j = 4<\/code>: Compare <code>12<\/code> with <code>11<\/code>, <code>11<\/code> is smaller.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Minimum found at index 4. Swap <code>64<\/code> and <code>11<\/code>.<\/li>\n\n\n\n<li><strong>Array after 1st iteration:<\/strong> 11,25,12,22,64<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>i = 1<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start with the second element <code>25<\/code> as the current minimum.<\/li>\n\n\n\n<li>Compare with elements:\n<ul class=\"wp-block-list\">\n<li><code>j = 2<\/code>: Compare <code>25<\/code> with <code>12<\/code>, <code>12<\/code> is smaller.<\/li>\n\n\n\n<li><code>j = 3<\/code>: Compare <code>12<\/code> with <code>22<\/code>, <code>12<\/code> remains smaller.<\/li>\n\n\n\n<li><code>j = 4<\/code>: Compare <code>12<\/code> with <code>64<\/code>, <code>12<\/code> remains smaller.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Minimum found at index 2. Swap <code>25<\/code> and <code>12<\/code>.<\/li>\n\n\n\n<li><strong>Array after 2nd iteration:<\/strong> 11,12,25,22,6411, 12, 25, 22, 6411,12,25,22,64<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>i = 2<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start with the third element <code>25<\/code> as the current minimum.<\/li>\n\n\n\n<li>Compare with elements:\n<ul class=\"wp-block-list\">\n<li><code>j = 3<\/code>: Compare <code>25<\/code> with <code>22<\/code>, <code>22<\/code> is smaller.<\/li>\n\n\n\n<li><code>j = 4<\/code>: Compare <code>22<\/code> with <code>64<\/code>, <code>22<\/code> remains smaller.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>Minimum found at index 3. Swap <code>25<\/code> and <code>22<\/code>.<\/li>\n\n\n\n<li><strong>Array after 3rd iteration:<\/strong> 11,12,25,22,64<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>i = 3<\/strong>\n<ul class=\"wp-block-list\">\n<li>Start with the fourth element <code>25<\/code> as the current minimum.<\/li>\n\n\n\n<li>Compare with elements:\n<ul class=\"wp-block-list\">\n<li><code>j = 4<\/code>: Compare <code>25<\/code> with <code>64<\/code>, <code>25<\/code> remains smaller.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>No swap needed since <code>25<\/code> is already the minimum.<\/li>\n\n\n\n<li><strong>Array after 4th iteration:<\/strong> 11,12,22,25,64<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>i = 4<\/strong>\n<ul class=\"wp-block-list\">\n<li>The final element <code>64<\/code> is already in its correct place, so no action is needed.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Final Sorted Array<\/h3>\n\n\n\n<p>11,12,22,25,64<\/p>\n\n\n\n<p>This step-by-step explanation shows how the Selection Sort algorithm works by repeatedly finding the minimum element in the unsorted portion of the array and swapping it with the first unsorted element until the entire array is sorted.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Loop In variants and Insertion Sort <\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\ud835\udc0b\ud835\udc1e\ud835\udc1c\ud835\udc2d\ud835\udc2e\ud835\udc2b\ud835\udc1e-\ud835\udfd0 : \ud835\udc0b\ud835\udc28\ud835\udc28\ud835\udc29 \ud835\udc22\ud835\udc27\ud835\udc2f\ud835\udc1a\ud835\udc2b\ud835\udc22\ud835\udc1a\ud835\udc27\ud835\udc2d \ud835\udc1a\ud835\udc27\ud835\udc1d \ud835\udc02\ud835\udc28\ud835\udc2b\ud835\udc2b\ud835\udc1e\ud835\udc1c\ud835\udc2d\ud835\udc27\ud835\udc1e\ud835\udc2c\ud835\udc2c  \ud835\udc28\ud835\udc1f \ud835\udc1a\ud835\udc27 \ud835\udc00\ud835\udc25\ud835\udc20\ud835\udc28\ud835\udc2b\ud835\udc22\ud835\udc2d\ud835\udc21\ud835\udc26.\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/H69reks2FOs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><strong>Insertion Sort i<\/strong>s a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.<\/p>\n\n\n\n<p>Here&#8217;s the Insertion Sort algorithm.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void insertionSort(int arr&#91;], int n) {\n    int i, key, j;\n    for (i = 1; i &lt; n; i++) {  \/\/ Start with the second element (index 1)\n        key = arr&#91;i];          \/\/ The element to be inserted into the sorted part\n        j = i - 1;             \/\/ Index of the previous element\n\n        \/\/ Move elements of arr&#91;0..i-1] that are greater than key to one position ahead of their current position\n        while (j &gt;= 0 &amp;&amp; arr&#91;j] &gt; key) {\n            arr&#91;j + 1] = arr&#91;j];\n            j = j - 1;\n        }\n        arr&#91;j + 1] = key;  \/\/ Place the key in its correct position\n    }\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Explanation of Each Step<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>i<\/code> is the loop variable that starts from the second element (index 1) because the first element is considered already sorted.<\/li>\n\n\n\n<li><code>key<\/code> holds the value of the element to be inserted into the correct position in the sorted portion of the array.<\/li>\n\n\n\n<li><code>j<\/code> is used to scan through the sorted portion of the array, which is on the left side of the current element <code>key<\/code>.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Outer Loop<\/strong> (<code>for<\/code> loop):<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>This loop runs from the second element to the last element (<code>i = 1<\/code> to <code>n-1<\/code>).<\/li>\n\n\n\n<li>Each iteration considers the element <code>arr[i]<\/code> as the <code>key<\/code> and tries to insert it into the sorted part of the array on its left side.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Inner Loop<\/strong> (<code>while<\/code> loop):<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>This loop moves elements in the sorted portion of the array (left of <code>i<\/code>) that are greater than the <code>key<\/code> one position to the right to make space for the <code>key<\/code>.<\/li>\n\n\n\n<li>The loop continues as long as there are elements on the left that are greater than the <code>key<\/code> and as long as <code>j<\/code> is not negative (indicating the beginning of the array).<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Insert the Key<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>After shifting elements, the correct position for the <code>key<\/code> is found, and it is placed at <code>arr[j + 1]<\/code>.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>End of Outer Loop<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Once the <code>for<\/code> loop completes, the array is fully sorted in ascending order.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Example<\/h3>\n\n\n\n<p>For an array <code>arr = [5, 2, 9, 1, 5, 6]<\/code>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>1st iteration (<code>i=1<\/code>)<\/strong>: Insert <code>2<\/code> into <code>[5]<\/code> \u2192 <code>[2, 5]<\/code><\/li>\n\n\n\n<li><strong>2nd iteration (<code>i=2<\/code>)<\/strong>: Insert <code>9<\/code> into <code>[2, 5]<\/code> \u2192 <code>[2, 5, 9]<\/code><\/li>\n\n\n\n<li><strong>3rd iteration (<code>i=3<\/code>)<\/strong>: Insert <code>1<\/code> into <code>[2, 5, 9]<\/code> \u2192 <code>[1, 2, 5, 9]<\/code><\/li>\n\n\n\n<li><strong>4th iteration (<code>i=4<\/code>)<\/strong>: Insert <code>5<\/code> into <code>[1, 2, 5, 9]<\/code> \u2192 <code>[1, 2, 5, 5, 9]<\/code><\/li>\n\n\n\n<li><strong>5th iteration (<code>i=5<\/code>)<\/strong>: Insert <code>6<\/code> into <code>[1, 2, 5, 5, 9]<\/code> \u2192 <code>[1, 2, 5, 5, 6, 9]<\/code><\/li>\n<\/ul>\n\n\n\n<p>Final sorted array: <code>[1, 2, 5, 5, 6, 9]<\/code>.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Loop Invariant and Proof of Correctness in Insertion Sort<\/h3>\n\n\n\n<p>A <strong>loop invariant<\/strong> is a condition that holds true before and after each iteration of a loop. It helps in reasoning about the correctness of an algorithm.<\/p>\n\n\n\n<p>For the Insertion Sort algorithm, the loop invariant is:<\/p>\n\n\n\n<p><strong>Invariant:<\/strong> At the start of each iteration of the outer loop (with index <code>i<\/code>), the subarray <code>arr[0..i-1]<\/code> consists of the elements that were originally in <code>arr[0..i-1]<\/code> but in sorted order.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Steps to Prove Correctness<\/h3>\n\n\n\n<p>To prove the correctness of the Insertion Sort algorithm using the loop invariant, we must demonstrate three things:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>: The loop invariant is true before the first iteration.<\/li>\n\n\n\n<li><strong>Maintenance<\/strong>: If the loop invariant is true before an iteration of the loop, it remains true before the next iteration.<\/li>\n\n\n\n<li><strong>Termination<\/strong>: When the loop terminates, the loop invariant gives us a useful property that helps prove the algorithm is correct.<\/li>\n<\/ol>\n\n\n\n<h4 class=\"wp-block-heading\">1. Initialization<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Before the first iteration (<code>i = 1<\/code>), the subarray <code>arr[0..0]<\/code> contains only one element (<code>arr[0]<\/code>), which is trivially sorted.<\/li>\n\n\n\n<li>Therefore, the loop invariant holds true before the first iteration.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">2. Maintenance<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Assume that the loop invariant holds at the start of an iteration for <code>i = k<\/code>, meaning the subarray <code>arr[0..k-1]<\/code> is sorted.<\/li>\n\n\n\n<li>During this iteration, the algorithm selects the element <code>arr[k]<\/code> (denoted as <code>key<\/code>) and compares it to the elements in the sorted subarray <code>arr[0..k-1]<\/code>.<\/li>\n\n\n\n<li>The inner loop shifts all elements greater than <code>key<\/code> one position to the right, making space for <code>key<\/code> in its correct position.<\/li>\n\n\n\n<li>After placing <code>key<\/code> at the correct position, the subarray <code>arr[0..k]<\/code> is sorted.<\/li>\n\n\n\n<li>Hence, the loop invariant holds true at the end of this iteration, ensuring that the subarray <code>arr[0..k]<\/code> is sorted.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">3. Termination<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The outer loop terminates when <code>i = n<\/code>, where <code>n<\/code> is the length of the array.<\/li>\n\n\n\n<li>At this point, the loop invariant tells us that the subarray <code>arr[0..n-1]<\/code> (i.e., the entire array) is sorted.<\/li>\n\n\n\n<li>Therefore, the entire array is sorted when the algorithm completes.<\/li>\n<\/ul>\n\n\n\n<p>By proving that the loop invariant holds throughout the execution of the loop, we have demonstrated the correctness of the Insertion Sort algorithm. The algorithm sorts the array in ascending order as intended. Let&#8217;s analyze the time complexity of the Insertion Sort algorithm step by step. We will examine the time complexity for each part of the algorithm and then sum them up to get the overall time complexity.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Insertion Sort Algorithm (time consumes for each steps)<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>void insertionSort(int arr&#91;], int n) {\n    int i, key, j;\n\n    for (i = 1; i &lt; n; i++) {           \/\/ Step 1: Outer loop runs (n-1) times\n        key = arr&#91;i];                   \/\/ Step 2: Assignment operation (1 time per iteration)\n        j = i - 1;                      \/\/ Step 3: Assignment operation (1 time per iteration)\n\n        \/\/ Step 4: Inner loop - runs while j &gt;= 0 and arr&#91;j] &gt; key\n        while (j &gt;= 0 &amp;&amp; arr&#91;j] &gt; key) {\n            arr&#91;j + 1] = arr&#91;j];        \/\/ Step 5: Shifting elements (1 time per shift)\n            j = j - 1;                  \/\/ Step 6: Decrementing j (1 time per iteration)\n        }\n\n        arr&#91;j + 1] = key;               \/\/ Step 7: Insertion operation (1 time per iteration)\n    }\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Detailed Time Complexity Analysis<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Step 1: Outer Loop (<code>for (i = 1; i &lt; n; i++)<\/code>)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: The outer loop runs <code>(n-1)<\/code> times. Therefore, the time complexity for the outer loop is <code>O(n)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 2: Assigning <code>key = arr[i]<\/code><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: This is a constant-time operation, and it is executed <code>(n-1)<\/code> times (once in each iteration of the outer loop). Therefore, the total time complexity for this step is <code>O(n)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 3: Assigning <code>j = i - 1<\/code><\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: This is also a constant-time operation, executed <code>(n-1)<\/code> times. Thus, its total time complexity is <code>O(n)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 4: Inner Loop (<code>while (j &gt;= 0 &amp;&amp; arr[j] &gt; key)<\/code>)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>:<\/li>\n\n\n\n<li>In the worst case (reverse sorted array), the inner loop runs <code>i<\/code> times for each iteration of the outer loop.<\/li>\n\n\n\n<li>The first iteration of the outer loop (<code>i = 1<\/code>) has the inner loop running <code>1<\/code> time.<\/li>\n\n\n\n<li>The second iteration (<code>i = 2<\/code>) has the inner loop running <code>2<\/code> times, and so on, up to <code>(n-1)<\/code> times.<\/li>\n\n\n\n<li>The total number of iterations of the inner loop across all iterations of the outer loop is:<br>[<br>1 + 2 + 3 + &#8230;&#8230;. + (n-1) = n(n-1)\/2<br>]<\/li>\n\n\n\n<li>Therefore, the time complexity for the inner loop in the worst case is <code>O(n^2)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 5: Shifting Elements (<code>arr[j + 1] = arr[j]<\/code>)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: This operation is performed every time the inner loop condition is met. Therefore, it has the same complexity as the inner loop: <code>O(n^2)<\/code> in the worst case.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 6: Decrementing <code>j<\/code> (<code>j = j - 1<\/code>)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: This is a constant-time operation, but since it&#8217;s part of the inner loop, its total time complexity is <code>O(n^2)<\/code> in the worst case.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Step 7: Inserting the <code>key<\/code> (<code>arr[j + 1] = key<\/code>)<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity<\/strong>: This is a constant-time operation performed once per iteration of the outer loop, giving it a total time complexity of <code>O(n)<\/code>.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Total Time Complexity<\/h3>\n\n\n\n<p>Now, let&#8217;s sum up the time complexities of all these steps:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Outer loop<\/strong>: <code>O(n)<\/code><\/li>\n\n\n\n<li><strong>Assigning <code>key<\/code><\/strong>: <code>O(n)<\/code><\/li>\n\n\n\n<li><strong>Assigning <code>j<\/code><\/strong>: <code>O(n)<\/code><\/li>\n\n\n\n<li><strong>Inner loop<\/strong>: <code>O(n^2)<\/code><\/li>\n\n\n\n<li><strong>Shifting elements<\/strong>: <code>O(n^2)<\/code><\/li>\n\n\n\n<li><strong>Decrementing <code>j<\/code><\/strong>: <code>O(n^2)<\/code><\/li>\n\n\n\n<li><strong>Inserting the <code>key<\/code><\/strong>: <code>O(n)<\/code><\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Overall Time Complexity<\/h3>\n\n\n\n<p>The dominant term in this sum is <code>O(n^2)<\/code> (from the inner loop, shifting elements, and decrementing <code>j<\/code>). Therefore, the overall time complexity of the Insertion Sort algorithm is:  O(n^2) .This is true for the worst case and average case. In the best case, where the array is already sorted, the inner loop doesn\u2019t run, and the overall time complexity reduces to <code>O(n)<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Bubble Sort and its analysis<\/strong><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">Bubble Sort <\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">Overview<\/h4>\n\n\n\n<p>Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly traversing the array, comparing adjacent elements, and swapping them if they are in the wrong order. The process is repeated until the array is completely sorted. Though easy to implement, Bubble Sort is inefficient for large datasets.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Algorithm<\/h4>\n\n\n\n<p>Below is the algorithm of Bubble Sort algorithm:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>void bubbleSort(int arr&#91;], int n) {\n    int i, j, temp;\n    for (i = 0; i &lt; n-1; i++) {             \/\/ Outer loop for passes\n        for (j = 0; j &lt; n-i-1; j++) {       \/\/ Inner loop for each pair\n            if (arr&#91;j] &gt; arr&#91;j+1]) {        \/\/ Compare adjacent elements\n                \/\/ Swap arr&#91;j] and arr&#91;j+1]\n                temp = arr&#91;j];\n                arr&#91;j] = arr&#91;j+1];\n                arr&#91;j+1] = temp;\n            }\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">Explanation<\/h4>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The algorithm begins by initializing two loops. The outer loop (<code>i<\/code>) runs <code>n-1<\/code> times, where <code>n<\/code> is the number of elements in the array. This ensures that each element is checked and placed in its correct position.<\/li>\n\n\n\n<li>The inner loop (<code>j<\/code>) iterates through the array, comparing adjacent elements and swapping them if they are in the wrong order.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Swapping<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If the current element <code>arr[j]<\/code> is greater than the next element <code>arr[j+1]<\/code>, they are swapped. The swap is done using a temporary variable <code>temp<\/code>.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Optimization (Optional)<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>To optimize, you can add a flag to detect if any swaps were made in an iteration. If no swaps are made, the array is already sorted, and the algorithm can terminate early.<\/li>\n<\/ul>\n\n\n\n<pre class=\"wp-block-code\"><code>   void bubbleSort(int arr&#91;], int n) {\n       int i, j, temp;\n       bool swapped;\n       for (i = 0; i &lt; n-1; i++) {\n           swapped = false;\n           for (j = 0; j &lt; n-i-1; j++) {\n               if (arr&#91;j] &gt; arr&#91;j+1]) {\n                   temp = arr&#91;j];\n                   arr&#91;j] = arr&#91;j+1];\n                   arr&#91;j+1] = temp;\n                   swapped = true;\n               }\n           }\n           if (!swapped) break;  \/\/ If no elements were swapped, break\n       }\n   }<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">Time Complexity<\/h4>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Best Case<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>O(n)<\/strong>: If the array is already sorted, the inner loop will run without making any swaps. In the optimized version with a swap flag, the algorithm will terminate after the first pass.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Worst Case<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>O(n^2)<\/strong>: This occurs when the array is sorted in reverse order. In this scenario, each element will have to be swapped in every iteration of the inner loop.<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Average Case<\/strong>:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>O(n^2)<\/strong>: In general, Bubble Sort will take quadratic time because most elements will need to be swapped as the algorithm progresses.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Space Complexity<\/h4>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>O(1)<\/strong>: Bubble Sort is an in-place sorting algorithm, meaning it requires a constant amount of additional memory space regardless of the input size.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Summary<\/h4>\n\n\n\n<p>Bubble Sort is an intuitive and easy-to-understand algorithm. However, due to its inefficiency on large datasets, it is rarely used in practice when more efficient sorting algorithms like Quick Sort or Merge Sort are available. Despite its simplicity, it serves as a good introductory algorithm for learning the basics of sorting and algorithm optimization.<\/p>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>QUICK SORT<\/strong><\/h2>\n\n\n\n<p>Quicksort is an efficient sorting algorithm with a worst-case running time of O(n\u00b2) when sorting an array of n numbers. Despite this, quicksort is often the best practical choice due to its average-case performance, with an expected running time of O(n log n) when all elements are distinct. The constant factors in the O(n log n) notation are small, making it more efficient than other algorithms like merge sort. Moreover, quicksort has the advantage of sorting in place, which is particularly useful in virtual memory environments.<\/p>\n\n\n\n<p>Quicksort follows the divide-and-conquer paradigm with three steps:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Divide:<\/strong> The array is partitioned into two subarrays. Elements smaller than or equal to the pivot are placed in the lower subarray, while those greater than or equal to the pivot are placed in the higher subarray. The pivot&#8217;s index is determined during this partitioning.<\/li>\n\n\n\n<li><strong>Conquer:<\/strong> Quicksort is called recursively on the two subarrays to sort them.<\/li>\n\n\n\n<li><strong>Combine:<\/strong> No explicit combination is needed since the subarrays are already sorted, making the entire array sorted once the recursion completes.<\/li>\n<\/ol>\n\n\n\n<p>The algorithm performs well on average, and a randomized version can further improve its performance by reducing the chance of encountering the worst-case scenario. When distinct elements are present, the randomized version ensures a good expected running time, avoiding worst-case behavior.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"902\" height=\"235\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/1-1.png\" alt=\"\" class=\"wp-image-940\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/1-1.png 902w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/1-1-300x78.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/1-1-768x200.png 768w\" sizes=\"auto, (max-width: 902px) 100vw, 902px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Partitioning the Array<\/h3>\n\n\n\n<p>The key to quicksort is the <strong>PARTITION<\/strong> procedure, which rearranges a subarray in place and returns the index that divides the subarray into two parts. The process separates elements into those less than or equal to the pivot and those greater than or equal to the pivot.<\/p>\n\n\n\n<p>In this procedure, the pivot element is always selected as the last element of the subarray, denoted by <code>A[r]<\/code>. As the algorithm progresses, elements are divided into four distinct regions, though some regions may be empty. These regions represent:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Elements smaller than or equal to the pivot.<\/li>\n\n\n\n<li>Elements greater than or equal to the pivot.<\/li>\n\n\n\n<li>The pivot itself.<\/li>\n\n\n\n<li>The region yet to be processed.<\/li>\n<\/ol>\n\n\n\n<p>The properties of these regions are maintained by a loop invariant, ensuring that after each iteration of the loop, the elements are properly partitioned around the pivot.<\/p>\n\n\n\n<p>This process is illustrated with an 8-element array, where <strong>PARTITION<\/strong> correctly divides the array by placing the pivot in its correct position and returning the index where the partition occurs.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"897\" height=\"326\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/2-1.png\" alt=\"\" class=\"wp-image-941\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/2-1.png 897w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/2-1-300x109.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/2-1-768x279.png 768w\" sizes=\"auto, (max-width: 897px) 100vw, 897px\" \/><\/figure>\n\n\n\n<p>At the beginning of each iteration of the loop in the <strong>PARTITION<\/strong> procedure, the following conditions, known as the <strong>loop invariant<\/strong>, hold for any index <code>k<\/code> in the array:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>For <code>p \u2264 k \u2264 i<\/code>:<\/strong> The elements in this region (<code>A[k] \u2264 x<\/code>) are less than or equal to the pivot <code>x<\/code>. This corresponds to the tan region in below figure.<\/li>\n\n\n\n<li><strong>For <code>i + 1 \u2264 k \u2264 j - 1<\/code>:<\/strong> The elements in this region (<code>A[k] &gt; x<\/code>) are greater than the pivot. This corresponds to the blue region.<\/li>\n\n\n\n<li><strong>For <code>k = r<\/code>:<\/strong> The element at this position (<code>A[k] = x<\/code>) is equal to the pivot itself. This corresponds to the yellow region.<\/li>\n<\/ol>\n\n\n\n<p>To ensure the correctness of the algorithm:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong> Before the first iteration, these conditions hold as the initial regions are set properly, with <code>i<\/code> and <code>j<\/code> indicating the boundaries.<\/li>\n\n\n\n<li><strong>Maintenance:<\/strong> Each iteration of the loop maintains this invariant. During the partitioning process, elements are moved between regions while maintaining the relative order and boundaries set by the loop invariant.<\/li>\n\n\n\n<li><strong>Termination:<\/strong> When the loop terminates, all elements in the subarray have been processed according to the invariant. At this point, the pivot element is correctly positioned, and the array is partitioned into two regions: elements less than or equal to the pivot on one side, and elements greater than or equal to the pivot on the other.<\/li>\n<\/ul>\n\n\n\n<p>The correctness of the algorithm follows from this invariant, ensuring that after partitioning, the pivot is in its correct final position.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Initialization:<\/h3>\n\n\n\n<p>Before the first iteration of the loop, the indices <code>i = p - 1<\/code> and <code>j = p<\/code>. At this point:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>No values exist between <code>p<\/code> and <code>i<\/code>, and no values lie between <code>i + 1<\/code> and <code>j - 1<\/code>. Thus, the first two conditions of the loop invariant are trivially satisfied because these regions are empty.<\/li>\n\n\n\n<li>The third condition is satisfied by the assignment made in line 1, which ensures that the pivot is correctly initialized.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Maintenance:<\/h3>\n\n\n\n<p>There are two possible outcomes for each iteration, based on the comparison in line 4 of the algorithm:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Case 1:<\/strong> If <code>A[j] &gt; x<\/code>, the loop increments <code>j<\/code>. Since no elements are swapped, the second condition of the loop invariant holds for <code>A[j - 1]<\/code> (the current position of <code>j<\/code>), and no other values in the array are affected.<\/li>\n\n\n\n<li><strong>Case 2:<\/strong> If <code>A[j] \u2264 x<\/code>, the loop increments <code>i<\/code>, swaps <code>A[i]<\/code> with <code>A[j]<\/code>, and then increments <code>j<\/code>. After the swap:<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The element <code>A[i]<\/code> satisfies the first condition (<code>A[i] \u2264 x<\/code>), maintaining the region where elements are less than or equal to the pivot.<\/li>\n\n\n\n<li>The element <code>A[j - 1]<\/code> (previously swapped) satisfies the second condition (<code>A[j - 1] &gt; x<\/code>), maintaining the region where elements are greater than the pivot.<\/li>\n<\/ul>\n\n\n\n<p>This process ensures that the loop invariant holds after each iteration.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Termination:<\/h3>\n\n\n\n<p>The loop iterates exactly <code>r - p<\/code> times, eventually terminating when <code>j = r<\/code>. At this point, the unexamined subarray from <code>A[j]<\/code> to <code>A[r - 1]<\/code> is empty, and every element in the array satisfies one of the three conditions:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Elements less than or equal to the pivot <code>x<\/code>.<\/li>\n\n\n\n<li>Elements greater than <code>x<\/code>.<\/li>\n\n\n\n<li>The pivot element itself.<\/li>\n<\/ol>\n\n\n\n<p>Thus, the array is successfully partitioned into three sets: the low side (less than or equal to <code>x<\/code>), the high side (greater than <code>x<\/code>), and the pivot, which is now in its correct position.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"427\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/3-1024x427.png\" alt=\"\" class=\"wp-image-942\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/3-1024x427.png 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/3-300x125.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/3-768x320.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/3.png 1356w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>The final two lines of the <strong>PARTITION<\/strong> procedure complete the process by swapping the pivot with the leftmost element that is greater than the pivot (<code>x<\/code>). This operation ensures that the pivot is moved into its correct position in the partitioned array.<\/p>\n\n\n\n<p>After this swap, the pivot is placed in its final sorted position, and the procedure returns the new index of the pivot.<\/p>\n\n\n\n<p>At this point, the output of <strong>PARTITION<\/strong> satisfies the requirements of the divide step in quicksort. Specifically:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>All elements to the left of the pivot are less than or equal to the pivot.<\/li>\n\n\n\n<li>All elements to the right of the pivot are greater than the pivot.<\/li>\n<\/ul>\n\n\n\n<p>In fact, the partitioning ensures an even stronger condition: after line 3 of <strong>QUICKSORT<\/strong>, the element at index <code>q<\/code> (the pivot) is strictly less than every element in the subarray from <code>q + 1<\/code> to <code>r<\/code>. This guarantees that the pivot is correctly positioned, and the array is properly divided for the recursive steps of quicksort.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"427\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/5-4-1024x427.png\" alt=\"\" class=\"wp-image-944\" style=\"width:677px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/5-4-1024x427.png 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/5-4-300x125.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/5-4-768x320.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/5-4.png 1356w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"685\" height=\"234\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/6.png\" alt=\"\" class=\"wp-image-946\" style=\"width:597px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/6.png 685w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/6-300x102.png 300w\" sizes=\"auto, (max-width: 685px) 100vw, 685px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"752\" height=\"446\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/7.jpg\" alt=\"\" class=\"wp-image-947\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/7.jpg 752w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/7-300x178.jpg 300w\" sizes=\"auto, (max-width: 752px) 100vw, 752px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading has-text-align-center\" id=\"Merge\"><strong>Merge Sort<\/strong><\/h3>\n\n\n\n<p>Merge sort is a divide-and-conquer algorithm that recursively splits an array into two halves until each subarray contains only one element, which is considered sorted. It then merges these smaller sorted subarrays back together in a way that results in a sorted array. The merging process compares elements from the two subarrays, placing the smaller element into the result array at each step, and continues until all elements from both subarrays are merged. This process ensures that the entire array is sorted as the subarrays are combined. Merge sort consistently operates with a time complexity of O(n log n), making it efficient for large datasets.<\/p>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"773\" height=\"420\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/MergeUpdate.jpg\" alt=\"\" class=\"wp-image-1226\" style=\"width:1227px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/MergeUpdate.jpg 773w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/MergeUpdate-300x163.jpg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/MergeUpdate-768x417.jpg 768w\" sizes=\"auto, (max-width: 773px) 100vw, 773px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"546\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/WhatsApp-Image-2024-10-03-at-12.50.45-1024x546.jpeg\" alt=\"\" class=\"wp-image-1224\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/WhatsApp-Image-2024-10-03-at-12.50.45-1024x546.jpeg 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/WhatsApp-Image-2024-10-03-at-12.50.45-300x160.jpeg 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/WhatsApp-Image-2024-10-03-at-12.50.45-768x409.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/WhatsApp-Image-2024-10-03-at-12.50.45-rotated.jpeg 1280w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"572\" height=\"554\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/Merge_Sort.jpg\" alt=\"\" class=\"wp-image-1230\" style=\"width:1018px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/Merge_Sort.jpg 572w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/Merge_Sort-300x291.jpg 300w\" sizes=\"auto, (max-width: 572px) 100vw, 572px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"MERGE SORT\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/HsfDPRu0b5o?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\" id=\"Counting\"><img loading=\"lazy\" decoding=\"async\" width=\"760\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29-760x1024.jpeg\" alt=\"\" class=\"wp-image-1210\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29-760x1024.jpeg 760w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29-223x300.jpeg 223w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29-768x1035.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29-1140x1536.jpeg 1140w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-30-at-00.13.29.jpeg 1187w\" sizes=\"auto, (max-width: 760px) 100vw, 760px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Trees<\/strong><\/h2>\n\n\n\n<h2 class=\"wp-block-heading\"> Binary Trees <\/h2>\n\n\n\n<p>A binary tree is a fundamental data structure in computer science, characterized by its hierarchical structure where each node can have a maximum of two children. The term &#8220;binary&#8221; directly implies that each node in the tree can have zero, one, or two children. This simple yet powerful structure forms the basis for many algorithms and is widely used in various applications such as expression parsing, searching algorithms, and decision-making processes.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">What is a Binary Tree?<\/h3>\n\n\n\n<p>A binary tree is a collection of nodes arranged in a hierarchy. The topmost node is called the root, and each node contains pointers to its left and right children. If a node has no children, it is called a leaf node. If a node has exactly one child, it is known as a degenerate or skewed node.<\/p>\n\n\n\n<p>For instance, consider the following simple binary tree:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>      1\n     \/ \\\n    2   3\n   \/ \\\n  4   5<\/code><\/pre>\n\n\n\n<p>In this binary tree:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Node 1 is the root with two children (nodes 2 and 3).<\/li>\n\n\n\n<li>Node 2 has two children (nodes 4 and 5).<\/li>\n\n\n\n<li>Nodes 3, 4, and 5 are leaf nodes as they do not have any children.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Properties of a Binary Tree<\/h3>\n\n\n\n<p>Binary trees have several important properties that are crucial for understanding their structure and behavior:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Maximum Nodes at Level i<\/strong>: At any level ( i ), the maximum number of nodes that can exist is ( 2^i ). For example, at level 0 (the root level), there can be ( 2^0 = 1 ) node, at level 1 there can be ( 2^1 = 2 ) nodes, and so on.<\/li>\n\n\n\n<li><strong>Height of the Tree<\/strong>: The height of a binary tree is the length of the longest path from the root to a leaf node. The height determines several other properties of the tree, including its maximum number of nodes and its minimum height.<\/li>\n\n\n\n<li><strong>Maximum Number of Nodes<\/strong>: The maximum number of nodes in a binary tree of height ( h ) is ( 2^{h+1} &#8211; 1 ). This formula accounts for the fact that each level can hold twice as many nodes as the previous level.<\/li>\n\n\n\n<li><strong>Minimum Height of a Tree<\/strong>: If a binary tree contains ( n ) nodes, its minimum height can be calculated as ( \\log_2(n+1) &#8211; 1 ).<\/li>\n\n\n\n<li><strong>Minimum Number of Nodes<\/strong>: Conversely, if a binary tree has a certain height ( h ), the minimum number of nodes it can have is ( h + 1 ). This occurs in a degenerate tree where each node only has one child.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Types of Binary Trees<\/h3>\n\n\n\n<p>Binary trees can be classified into several types based on the arrangement and properties of their nodes:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Full Binary Tree<\/strong>: A binary tree is considered full if every node has either zero or two children. In other words, no node in a full binary tree has only one child. This type of tree is also known as a proper or strict binary tree. <strong>Example:<\/strong><\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>         1\n        \/ \\\n       2   3\n      \/ \\\n     4   5<\/code><\/pre>\n\n\n\n<p>In this example, each node has either two children or none, making it a full binary tree.<\/p>\n\n\n\n<ol start=\"2\" class=\"wp-block-list\">\n<li><strong>Complete Binary Tree<\/strong>: A complete binary tree is a tree in which all levels are completely filled except possibly the last level, where all nodes are as left as possible. This structure ensures that the tree is as compact as possible, minimizing the tree&#8217;s height. <strong>Example:<\/strong><\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>         1\n        \/ \\\n       2   3\n      \/ \\  \/\n     4   5 6<\/code><\/pre>\n\n\n\n<p>In this example, the last level is not completely filled, but all nodes are as far left as possible.<\/p>\n\n\n\n<ol start=\"3\" class=\"wp-block-list\">\n<li><strong>Perfect Binary Tree<\/strong>: A perfect binary tree is a special case of both full and complete binary trees. In a perfect binary tree, all internal nodes have exactly two children, and all leaf nodes are at the same level. <strong>Example:<\/strong><\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>         1\n        \/ \\\n       2   3\n      \/ \\ \/ \\\n     4  5 6  7<\/code><\/pre>\n\n\n\n<p>Here, each node has exactly two children, and all leaf nodes (4, 5, 6, 7) are at the same level.<\/p>\n\n\n\n<ol start=\"4\" class=\"wp-block-list\">\n<li><strong>Degenerate (or Skewed) Binary Tree<\/strong>: A degenerate binary tree is a tree where each parent node has only one child. This structure effectively reduces the tree to a linked list, leading to inefficient operations compared to a balanced binary tree. <strong>Example (Right-Skewed):<\/strong><\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>   1\n    \\\n     2\n      \\\n       3\n        \\\n         4<\/code><\/pre>\n\n\n\n<p><strong>Example (Left-Skewed):<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>       1\n      \/\n     2\n    \/\n   3\n  \/\n 4<\/code><\/pre>\n\n\n\n<ol start=\"5\" class=\"wp-block-list\">\n<li><strong>Balanced Binary Tree<\/strong>: In a balanced binary tree, the difference in height between the left and right subtrees of any node is at most one. Balanced trees ensure that operations such as insertion, deletion, and lookup are performed efficiently. Common examples of balanced binary trees include AVL trees and Red-Black trees. <strong>Example:<\/strong><\/li>\n<\/ol>\n\n\n\n<pre class=\"wp-block-code\"><code>         1\n        \/ \\\n       2   3\n      \/   \/ \\\n     4   5   6<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Implementation of Binary Trees<\/h3>\n\n\n\n<p>Binary trees are commonly implemented using pointers, with each node typically represented as a structure or class containing the data and pointers to its left and right children.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>struct node {  \n    int data;  \n    struct node *left, *right;  \n};<\/code><\/pre>\n\n\n\n<p>In this structure, <code>data<\/code> represents the value stored in the node, while <code>left<\/code> and <code>right<\/code> are pointers to the node&#8217;s left and right children, respectively.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Creating a Binary Tree in C<\/h3>\n\n\n\n<p>To create a binary tree in C, we typically define a function that recursively constructs the tree by allocating memory for new nodes and assigning their children.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;stdio.h&gt;  \n#include&lt;stdlib.h&gt;\n\nstruct node {  \n    int data;  \n    struct node *left, *right;  \n};  \n\nstruct node* create() {  \n    struct node *temp;  \n    int data, choice;  \n    temp = (struct node *)malloc(sizeof(struct node));  \n\n    printf(\"Press 0 to exit\\n\");  \n    printf(\"Press 1 for new node\\n\");  \n    printf(\"Enter your choice: \");  \n    scanf(\"%d\", &amp;choice);   \n\n    if (choice == 0) {  \n        return NULL;  \n    } else {  \n        printf(\"Enter the data: \");  \n        scanf(\"%d\", &amp;data);  \n        temp-&gt;data = data;  \n        printf(\"Enter the left child of %d:\\n\", data);  \n        temp-&gt;left = create();  \n        printf(\"Enter the right child of %d:\\n\", data);  \n        temp-&gt;right = create();  \n        return temp;   \n    }  \n}  \n\nint main() {  \n    struct node *root;  \n    root = create();  \n    return 0;  \n}<\/code><\/pre>\n\n\n\n<p>In this code, the <code>create<\/code> function prompts the user to enter data for each node and recursively creates left and right children until the tree is fully constructed.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Tree Traversal Techniques<\/h3>\n\n\n\n<p>Traversing a binary tree means visiting each node in a specific order. There are three primary traversal methods:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Inorder Traversal<\/strong>: Visit the left subtree, the root node, and then the right subtree.<\/li>\n\n\n\n<li><strong>Preorder Traversal<\/strong>: Visit the root node first, followed by the left and right subtrees.<\/li>\n\n\n\n<li><strong>Postorder Traversal<\/strong>: Visit the left and right subtrees before visiting the root node.<\/li>\n<\/ol>\n\n\n\n<p>Each traversal technique serves different purposes and can be used depending on the desired outcome of the operation.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Conclusion<\/h3>\n\n\n\n<p>Binary trees are a versatile and essential data structure in computer science, providing the foundation for many algorithms and systems. Understanding the properties, types, and implementation of binary trees is crucial for developing efficient solutions in various applications. With balanced trees ensuring optimal performance and different traversal techniques offering flexibility, binary trees remain a cornerstone in the field of data structures.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Here\u2019s a simple C code for creating and traversing a binary tree. The code includes functions to create nodes, insert nodes, and perform inorder, preorder, and postorder traversals.\n\n```c\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\n\/\/ Structure for a node in the binary tree\nstruct Node {\n    int data;\n    struct Node* left;\n    struct Node* right;\n};\n\n\/\/ Function to create a new node\nstruct Node* createNode(int data) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode-&gt;data = data;\n    newNode-&gt;left = NULL;\n    newNode-&gt;right = NULL;\n    return newNode;\n}\n\n\/\/ Function to insert a node in the binary tree\nstruct Node* insertNode(struct Node* root, int data) {\n    if (root == NULL) {\n        root = createNode(data);\n    } else if (data &lt;= root-&gt;data) {\n        root-&gt;left = insertNode(root-&gt;left, data);\n    } else {\n        root-&gt;right = insertNode(root-&gt;right, data);\n    }\n    return root;\n}\n\n\/\/ Function for Inorder Traversal (Left, Root, Right)\nvoid inorderTraversal(struct Node* root) {\n    if (root != NULL) {\n        inorderTraversal(root-&gt;left);\n        printf(\"%d \", root-&gt;data);\n        inorderTraversal(root-&gt;right);\n    }\n}\n\n\/\/ Function for Preorder Traversal (Root, Left, Right)\nvoid preorderTraversal(struct Node* root) {\n    if (root != NULL) {\n        printf(\"%d \", root-&gt;data);\n        preorderTraversal(root-&gt;left);\n        preorderTraversal(root-&gt;right);\n    }\n}\n\n\/\/ Function for Postorder Traversal (Left, Right, Root)\nvoid postorderTraversal(struct Node* root) {\n    if (root != NULL) {\n        postorderTraversal(root-&gt;left);\n        postorderTraversal(root-&gt;right);\n        printf(\"%d \", root-&gt;data);\n    }\n}\n\nint main() {\n    struct Node* root = NULL;\n    int choice, data;\n\n    while (1) {\n        printf(\"\\nBinary Tree Operations:\\n\");\n        printf(\"1. Insert Node\\n\");\n        printf(\"2. Inorder Traversal\\n\");\n        printf(\"3. Preorder Traversal\\n\");\n        printf(\"4. Postorder Traversal\\n\");\n        printf(\"5. Exit\\n\");\n        printf(\"Enter your choice: \");\n        scanf(\"%d\", &amp;choice);\n\n        switch (choice) {\n            case 1:\n                printf(\"Enter data to insert: \");\n                scanf(\"%d\", &amp;data);\n                root = insertNode(root, data);\n                break;\n            case 2:\n                printf(\"Inorder Traversal: \");\n                inorderTraversal(root);\n                printf(\"\\n\");\n                break;\n            case 3:\n                printf(\"Preorder Traversal: \");\n                preorderTraversal(root);\n                printf(\"\\n\");\n                break;\n            case 4:\n                printf(\"Postorder Traversal: \");\n                postorderTraversal(root);\n                printf(\"\\n\");\n                break;\n            case 5:\n                exit(0);\n            default:\n                printf(\"Invalid choice! Please try again.\\n\");\n        }\n    }\n\n    return 0;\n}\n<strong>Explanation:<\/strong>\n1. createNode(): Allocates memory for a new node and initializes its data, left, and right pointers.\n2. insertNode(): Recursively inserts a new node into the binary tree. The new node is inserted based on whether the data is less than or greater than the current node's data.\n3. inorderTraversal(): Traverses the tree in inorder sequence (left, root, right).\n4. preorderTraversal()**: Traverses the tree in preorder sequence (root, left, right).\n5. postorderTraversal()**: Traverses the tree in postorder sequence (left, right, root).\n\n\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>BINARY SEARCH TREE<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"321\" height=\"150\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/bintree.png\" alt=\"\" class=\"wp-image-917\" style=\"width:730px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/bintree.png 321w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/bintree-300x140.png 300w\" sizes=\"auto, (max-width: 321px) 100vw, 321px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"742\" height=\"372\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/binarysearch.jpg\" alt=\"\" class=\"wp-image-922\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/binarysearch.jpg 742w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/binarysearch-300x150.jpg 300w\" sizes=\"auto, (max-width: 742px) 100vw, 742px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Level-order traversal <\/strong><\/h2>\n\n\n\n<p>Level-order traversal of a Binary Search Tree (BST) is performed by visiting nodes level by level, starting from the root and moving from left to right across each level.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Example:<\/h3>\n\n\n\n<p>Consider the following BST:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>       10\n      \/   \\\n     6     15\n    \/ \\   \/  \\\n   3   8 12   18<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">Level-Order Traversal Steps:<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Start at the root node (Level 0):<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit: 10<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Move to Level 1:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit: 6, 15<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Move to Level 2:<\/strong><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Visit: 3, 8, 12, 18<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Result:<\/h3>\n\n\n\n<p>The level-order traversal for the above BST is: <strong>10, 6, 15, 3, 8, 12, 18<\/strong>.<\/p>\n\n\n\n<p>This traversal can be implemented using a queue data structure, where you first enqueue the root, then iteratively dequeue a node, visit it, and enqueue its children.<\/p>\n\n\n\n<p id=\"BinSearchTree\">BST<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Binary Search Tree|| Inorder , Preorder and  Postorder traversal| C code implementation\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/3l-7IsPmDts?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><figcaption class=\"wp-element-caption\">BST<\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Finding kth smallest element in BST<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\" id=\"kthsmall\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"406\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/KTH_SMALLEST_ELEMENT-1024x406.png\" alt=\"\" class=\"wp-image-1289\" style=\"width:949px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/KTH_SMALLEST_ELEMENT-1024x406.png 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/KTH_SMALLEST_ELEMENT-300x119.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/KTH_SMALLEST_ELEMENT-768x304.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/10\/KTH_SMALLEST_ELEMENT.png 1116w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h4 class=\"wp-block-heading has-text-align-center\" id=\"AVL\"><strong>Introduction to AVL Tree<\/strong><\/h4>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-768x1024.jpeg\" alt=\"\" class=\"wp-image-1048\" style=\"width:563px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32.jpeg 960w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-1-768x1024.jpeg\" alt=\"\" class=\"wp-image-1049\" style=\"width:619px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-1-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-1-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-1.jpeg 960w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"766\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-2-766x1024.jpeg\" alt=\"\" class=\"wp-image-1050\" style=\"width:645px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-2-766x1024.jpeg 766w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-2-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-2-768x1026.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-2.jpeg 958w\" sizes=\"auto, (max-width: 766px) 100vw, 766px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"773\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-4-773x1024.jpeg\" alt=\"\" class=\"wp-image-1053\" style=\"width:649px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-4-773x1024.jpeg 773w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-4-226x300.jpeg 226w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-4-768x1018.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.32-4.jpeg 966w\" sizes=\"auto, (max-width: 773px) 100vw, 773px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"764\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/LEFTRIGHT-764x1024.png\" alt=\"\" class=\"wp-image-1058\" style=\"width:646px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/LEFTRIGHT-764x1024.png 764w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/LEFTRIGHT-224x300.png 224w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/LEFTRIGHT-768x1029.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/LEFTRIGHT.png 955w\" sizes=\"auto, (max-width: 764px) 100vw, 764px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"768\" height=\"1024\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.33-1-768x1024.jpeg\" alt=\"\" class=\"wp-image-1054\" style=\"width:663px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.33-1-768x1024.jpeg 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.33-1-225x300.jpeg 225w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/WhatsApp-Image-2024-09-22-at-22.51.33-1.jpeg 960w\" sizes=\"auto, (max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"AVL Tree\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/9fPXyu8mC9I?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\"><strong>Finding Maximum and Minimum element in a BST<\/strong><\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code> <strong>Algorithm to Find Maximum Element in a Binary Tree<\/strong>\nfunction findMax(root):\n    if root is null:\n        return null  \/\/ Tree is empty\n\n    maxElement = root\n\n    \/\/ Traverse to the rightmost node\n    while maxElement.right is not null:\n        maxElement = maxElement.right\n\n    return maxElement  \/\/ Return the maximum element\n\n<strong> Algorithm to Find Minimum Element in a Binary Search Tree<\/strong>\n\nfunction findMin(root):\n    if root is null:\n        return null  \/\/ Tree is empty\n\n    minElement = root\n\n    \/\/ Traverse to the leftmost node\n    while minElement.left is not null:\n        minElement = minElement.left\n\n    return minElement  \/\/ Return the minimum element\n<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"734\" height=\"450\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/BST-MAX.png\" alt=\"\" class=\"wp-image-1078\" style=\"width:454px;height:auto\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/BST-MAX.png 734w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/BST-MAX-300x184.png 300w\" sizes=\"auto, (max-width: 734px) 100vw, 734px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"AVLDEL\"><strong>Deletion NODEs in AVL Tree<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"390\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/AVL-DELETION-5-1024x390.png\" alt=\"\" class=\"wp-image-1190\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/AVL-DELETION-5-1024x390.png 1024w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/AVL-DELETION-5-300x114.png 300w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/AVL-DELETION-5-768x292.png 768w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/09\/AVL-DELETION-5.png 1353w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>To delete a node in an AVL tree, first, perform a standard Binary Search Tree (BST) deletion: if the node is a leaf, remove it; if it has one child, replace it with its child; if it has two children, find the in-order successor or predecessor, replace the node, . After the deletion, update the balance factors of each ancestor node and rebalance the tree if needed. Rebalancing is done using rotations: Left-Left (LL), Right-Right (RR), Left-Right (LR), or Right-Left (RL), depending on the imbalance detected, ensuring the tree remains balanced.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Deletion of NODES in AVL tree ||  Replace with in-order predecessors or in order successor\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/hD-d03V2-tA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading has-text-align-center\" id=\"Hash\"><strong>Hashing<\/strong><\/h2>\n\n\n\n<p><strong>Overview of Hashing<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Hashing is a widely-used method to locate a specific element within a collection of data efficiently.<\/li>\n\n\n\n<li>It reduces the number of comparisons required for searching.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"703\" height=\"304\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Untitled.png\" alt=\"\" class=\"wp-image-1294\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Untitled.png 703w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Untitled-300x130.png 300w\" sizes=\"auto, (max-width: 703px) 100vw, 703px\" \/><\/figure>\n\n\n\n<p><strong>Benefits of Hashing<\/strong><\/p>\n\n\n\n<p>Unlike other search approaches:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Hashing offers exceptional efficiency.<\/li>\n\n\n\n<li>Its performance is independent of the number of elements present in the dataset.<\/li>\n\n\n\n<li>Search operations are completed in constant time complexity O(1)O(1).<\/li>\n<\/ul>\n\n\n\n<p><strong>How Hashing Works<\/strong><\/p>\n\n\n\n<p><strong>Hash Table<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Hashing uses a specific array-like structure called a <strong>hash table<\/strong> to store data.<\/li>\n\n\n\n<li>Items are placed in the hash table based on a calculated hash key value.<\/li>\n<\/ul>\n\n\n\n<p><strong>Hash Key Value<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A hash key value is a unique identifier that determines the storage location of an item in the hash table.<\/li>\n\n\n\n<li>It is derived using a mathematical hash function.<\/li>\n<\/ul>\n\n\n\n<p><strong>Hash Function<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The hash function takes a data item as input and produces a small integer output, referred to as the <strong>hash value<\/strong>.<\/li>\n\n\n\n<li>The hash value serves as the index to store the data in the hash table.<\/li>\n<\/ul>\n\n\n\n<p><strong>Types of Hash Functions<\/strong><\/p>\n\n\n\n<p>Common types of hash functions include:<\/p>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li><strong>Mid-Square Method<\/strong><\/li>\n\n\n\n<li><strong>Division Method<\/strong><\/li>\n\n\n\n<li><strong>Folding Method<\/strong><\/li>\n<\/ol>\n\n\n\n<p>The choice of hash function depends on the user\u2019s requirements.<\/p>\n\n\n\n<p><strong>Features of a Good Hash Function<\/strong><\/p>\n\n\n\n<p>A well-designed hash function has the following characteristics:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>It is computationally efficient.<\/li>\n\n\n\n<li>It minimizes collisions (where two keys map to the same index).<\/li>\n\n\n\n<li>It ensures an even distribution of keys across the hash table.<\/li>\n<\/ul>\n\n\n\n<p><strong>Searching Techniques Comparison<\/strong><\/p>\n\n\n\n<p>Traditional searching methods, such as linear search, binary search, or search trees, rely on the size of the dataset, which affects their time complexity:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Linear Search<\/strong>: O(n)O(n) for unsorted arrays of size nn.<\/li>\n\n\n\n<li><strong>Binary Search<\/strong>: O(log\u2061n)O(\\log n) for sorted arrays or binary search trees.<\/li>\n<\/ul>\n\n\n\n<p><strong>Drawbacks of Traditional Methods<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>As the dataset grows, the time taken to search increases significantly.<\/li>\n\n\n\n<li>This becomes a challenge for large-scale datasets.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Example of Hashing: Separate Chaining<\/strong><\/p>\n\n\n\n<p><strong>Problem Statement<\/strong><\/p>\n\n\n\n<p>Using the hash function <strong>key mod 7<\/strong>, insert the following sequence into a hash table:<br>50,700,76,85,92,73,10150, 700, 76, 85, 92, 73, 101<br>Use <strong>separate chaining<\/strong> to handle collisions.<\/p>\n\n\n\n<p><strong>Solution Steps<\/strong><\/p>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li><strong>Initialize the Hash Table<\/strong>\n<ul class=\"wp-block-list\">\n<li>The hash table should have 7 buckets (hash values range from 0 to 6).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Insert Items<\/strong>\n<ul class=\"wp-block-list\">\n<li>Calculate the hash value for each key:\n<ul class=\"wp-block-list\">\n<li>Key 50: 50mod\u2009\u20097=50 mod 7 = 1, stored in bucket 1.<\/li>\n\n\n\n<li>Key 700: 700mod\u2009\u20097=0700 mod 7 = 0, stored in bucket 0.<\/li>\n\n\n\n<li>Key 76: 76mod\u2009\u20097=76 mod 7 = 6, stored in bucket 6.<\/li>\n\n\n\n<li>Key 85: 85mod\u2009\u20097=85 mod 7 = 1, causing a collision. Add to bucket 1 using a linked list.<\/li>\n\n\n\n<li>Continue similarly for keys 92,73,92, 73, and 101, using linked lists where collisions occur.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"682\" height=\"403\" src=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Capture2.jpg\" alt=\"\" class=\"wp-image-1295\" srcset=\"https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Capture2.jpg 682w, https:\/\/cyberenlightener.com\/wp-content\/uploads\/2024\/11\/Capture2-300x177.jpg 300w\" sizes=\"auto, (max-width: 682px) 100vw, 682px\" \/><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Alternative Method: Open Addressing<\/strong><\/p>\n\n\n\n<p><strong>What is Open Addressing?<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In this method, all data is stored directly within the hash table.<\/li>\n\n\n\n<li>Unlike separate chaining, no external structures are used.<\/li>\n<\/ul>\n\n\n\n<p><strong>Techniques in Open Addressing<\/strong><\/p>\n\n\n\n<ol start=\"1\" class=\"wp-block-list\">\n<li><strong>Linear Probing<\/strong>: Sequentially checks the next bucket for empty space.\n<ul class=\"wp-block-list\">\n<li>Pros: Easy to implement.<\/li>\n\n\n\n<li>Cons: Suffers from clustering.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Quadratic Probing<\/strong>: Jumps to the i2i^2-th bucket in the ii-th iteration to resolve collisions.<\/li>\n\n\n\n<li><strong>Double Hashing<\/strong>: Applies a second hash function to determine the next bucket in case of a collision.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Operations in Open Addressing<\/strong><\/p>\n\n\n\n<p><strong>Insertion<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Compute the hash value for the key.<\/li>\n\n\n\n<li>If a collision occurs, probe according to the technique until an empty bucket is found.<\/li>\n<\/ul>\n\n\n\n<p><strong>Searching<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Calculate the hash value and inspect the corresponding bucket.<\/li>\n\n\n\n<li>Continue probing if the bucket does not contain the desired key until the key or an empty bucket is found.<\/li>\n<\/ul>\n\n\n\n<p><strong>Deletion<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Locate the key and remove it. Mark the bucket as \u201cdeleted.\u201d<\/li>\n\n\n\n<li>Deleted buckets are reused during insertion but not skipped during searches.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Summary of Open Addressing Techniques<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><td><strong>Feature<\/strong><\/td><td><strong>Linear Probing<\/strong><\/td><td><strong>Quadratic Probing<\/strong><\/td><td><strong>Double Hashing<\/strong><\/td><\/tr><\/thead><tbody><tr><td><strong>Primary Clustering<\/strong><\/td><td>Yes<\/td><td>No<\/td><td>No<\/td><\/tr><tr><td><strong>Secondary Clustering<\/strong><\/td><td>Yes<\/td><td>Yes<\/td><td>No<\/td><\/tr><tr><td><strong>Cache Performance<\/strong><\/td><td>Best<\/td><td>Moderate<\/td><td>Poor<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Load Factor (\u03b1\\alpha) in Open Addressing<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Load factor is the ratio of the number of stored elements to the total size of the table.<\/li>\n\n\n\n<li>For open addressing, \u03b1\\alpha lies between 0 and 1.<\/li>\n<\/ul>\n\n\n\n<p><strong>Why?<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>All data is stored within the hash table, so the table size is always sufficient for the stored items.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Practice Problem: Linear Probing<\/strong><\/p>\n\n\n\n<p>Using the hash function <strong>key mod 7<\/strong>, insert the following keys:<br>50,700,76,85,92,73,10150, 700, 76, 85, 92, 73, 101<br>Resolve collisions using <strong>linear probing<\/strong>.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"HASHING : QUADRATIC PROBING  || Data Structure\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/aIr1KfNDJy4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Topics Covered Algorithms and data structures are the bedrock of computer science. They provide the methods and frameworks needed to process data efficiently, ensuring that software performs optimally under various conditions. An understanding of algorithms and data structures enables developers to create programs that are not only correct but also efficient and scalable. Fundamentals of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"class_list":["post-692","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/692","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=692"}],"version-history":[{"count":101,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/692\/revisions"}],"predecessor-version":[{"id":1299,"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=\/wp\/v2\/pages\/692\/revisions\/1299"}],"wp:attachment":[{"href":"https:\/\/cyberenlightener.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=692"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}