Greedy Algorithms Checklist: 4 weeks free course

In this week, you will learn about the fundamental concepts and techniques of greedy algorithms. The links cover a range of problems such as assigning cookies to children, filling a knapsack, finding the smallest missing positive integer, and dividing numbers into two groups. The links explore how a greedy approach can be used to solve each problem optimally by making locally optimal choices at each step in the hope of achieving a global optimal solution.

Learn the conceptual basics of greedy algorithms and also learn when to use them.

Assign Cookies problem involves assigning cookies of different sizes to children with different greed levels such that the maximum number of children can be satisfied. The term "greed level" refers to the amount of cookies that each child desires. The greedy approach sorts the lists and iteratively checks for contentment by comparing the size of the cookie with the greedy level of the sibling. If the cookie size is greater than or equal to the greedy level, the sibling is considered contented, and the count is incremented.

Fractional Knapsack problem involves maximizing the total value of items that can be placed into a knapsack with a limited weight capacity. The naive approach involves trying all possible subsets of items and fractions to find the maximum profit. The greedy approach involves sorting the items in descending order of value/weight and then including them in the knapsack one-by-one until either the capacity is reached or there are no more items left. You can also dive deeper into different variations of the Knapsack Problem. The Unbounded Knapsack Problem involves maximizing the value of items that can be put into a knapsack of unlimited capacity, while the 0-1 Knapsack Problem involves choosing a subset of items to maximize value while staying within a knapsack's weight limit. The Bin Packing Problem involves packing items into bins of limited capacity while minimizing the number of bins used.

Remove K Digits to Make Smallest Number is the problem of removing K digits from a given number to make it the smallest possible number. The approach for this problem involves using the Monotonic Stack approach. A monotonic stack is a special type of stack that maintains a monotonic sequence of elements, either strictly increasing or strictly decreasing, as we move from the bottom to the top of the stack.

Learn how to find the smallest missing positive integer in an unsorted integer array in O(n) time and constant space complexity using a greedy approach with hashmaps. The brute force approach involves traversing the array multiple times and finding the next smallest integer each time. The sorting approach involves sorting the array and then finding the missing smallest positive integer by traversing from the start.

Smallest Subset with Sum Greater than All Other Elements is the problem of finding the smallest subset of a given set of integers with a sum greater than the sum of all the other elements. The naive approach involves finding all possible subsets of the given set and then their sum is compared with the sum of the remaining elements. The greedy approach involves sorting the array in descending order and selecting the largest elements that sum up to at least half of the total sum of the given array. We select the largest elements to minimize the length of the subset.

Minimum Fibonacci Terms with Given Sum explains how to find the minimum number of Fibonacci terms that sum up to a given number using a greedy algorithm approach. The approach involves iterating through the Fibonacci sequence in reverse order and selecting the largest Fibonacci number that is less than or equal to the remaining sum, then subtracting that number from the sum and repeating the process until the sum becomes zero. Another similar problem is finding the number of ways to represent a given number as the sum of k Fibonacci numbers. This can be solved using either a brute force approach or a recursive approach.

Divide Numbers from 1 to N into Two Groups with Minimum Difference is the problem of dividing numbers from 1 to N into two groups such that the difference between the sum of the two groups is minimum. The naive approach involves generating all subsets of the array, calculating the sum of each subset, computing the absolute sum difference between the two subsets, and updating the minimum difference. The greedy approach involves sorting the numbers in descending order and assigning them to two groups with the goal of minimizing the difference between their sums.

Learn about "Maximum/minimum problems", with a particular focus on greedy algorithms for solving problems related to finding the maximum or minimum values of a particular quantity. The links in this subcategory cover a range of problems, such as finding the largest and smallest numbers with a given number of digits and sum of digits, finding the largest cube formed by deleting minimum digits from a number, and maximizing the sum of the product of an array with its index subject to a given condition.

Largest Number with Given Number of Digits and Sum of Digits problem discusses an greedy algorithmic approach to finding the largest possible number with a specified number of digits and a given sum of those digits. It uses a while loop to add the digit 9 until the sum is greater than or equal to 9 and then adds the remaining sum as the last digit. The approach fills the remaining digits with 0s to obtain the largest possible number.

Smallest Number with Given Number of Digits and Digits Sum involves a greedy method for finding the smallest possible number with a specified number of digits and a given sum of those digits. It uses a loop to determine the value of each digit by subtracting the remaining sum from 9 until the remaining sum is less than 9, assigning the leftmost digit with the remaining sum.

Finding the Largest Cube Formed by Deleting Minimum Digits from a Number uses a greedy a technique to find the largest possible cube that can be formed by deleting a specified minimum number of digits from a given number. The brute force approach involves checking every subsequence of the number to see if it is a cube and comparing it with the maximum cube found so far. The greedy approach involves generating all perfect cubes from 1 to N, where N is the given number, and checking if the largest cube is a subsequence of the given number.

Maximize Sum of Array (i) is a problem where we are given an array of integers and we maximize the sum of a function of array indices. The naive approach involves generating all permutations of the array, computing the sum of the product of array elements with their respective indices for each permutation, and returning the maximum value. The greedy approach involves sorting the array in increasing order, multiplying the minimum value of i with the minimum value of arr[i], and computing the sum of the product of array elements with their respective indices from i=0 to n-1.

In "Scheduling Problems", you will learn about greedy algorithms which involve optimizing the scheduling of tasks or events based on certain criteria. Examples include the Activity Selection Problem, Scheduling to Minimize Lateness, and Shortest Job First CPU Scheduling, each using a different objective and constraints.

Activity Selection Problem involves selecting the maximum number of non-overlapping activities that can be performed in a single time slot, using a greedy algorithm approach. The approach sorts the activities in ascending order of their finish times and selects the first activity. It then selects the next activity that starts after the finish time of the previous activity, and repeats this process until no more activities can be selected.

Scheduling to Minimize Lateness involves scheduling a set of jobs with deadlines and processing times such that the maximum lateness is minimized. The approach sorts the requests in increasing order of their deadlines, calculates the start time for each request based on the previous requests' processing times, and computes the minimum lateness for the schedule. The approach outputs the minimum lateness for the schedule.

Learn about the Shortest Job First (SJF) CPU scheduling algorithm, which executes the process with the smallest required CPU time first. Throughput refers to the number of processes that are completed per unit of time, while turnaround time is the time taken to execute a process from the moment it enters the system until it completes execution. SJF algorithm aims to maximize the system's throughput and minimize the turnaround time by executing smaller processes first. The algorithm sorts a set of processes by their arrival and burst time. It then calculates the waiting time, completion time, and turn-around time for each process.

Graph based problems involve solving problems related to graphs, such as finding the minimum spanning tree or the maximum clique. These problems can be tackled using a greedy approach that iteratively makes locally optimal decisions to ultimately arrive at a globally optimal solution. Examples include Graph Colouring, Single Maximal Clique, and Kruskal's Minimum Spanning Tree Algorithm.

Learn about graph coloring algorithms and understand the greedy algorithm for graph coloring. The greedy approach for this problem involves coloring the vertices of a graph one by one, using the smallest possible color that has not been used by any previously colored vertices that are adjacent to the current vertex. This approach is greedy because it chooses the smallest available color for each vertex, without considering the impact of that choice on the colors assigned to the remaining vertices. You can also learn about other algorithms and techniques used to solve a variety of graph problems. The Wigderson algorithm is a randomized algorithm used for graph coloring. The Welsh-Powell algorithm is a greedy algorithm used for graph coloring. The Bipartite Checking BFS algorithm is used to check whether a given graph is bipartite or not using Breadth-First Search (BFS).

Greedy Approach to Find Single Maximal Clique involves finding the largest complete subgraph in a given graph. The approach involves starting with an arbitrary subgraph and growing it one vertex at a time by looping through the remaining vertices. For each vertex, it is added to the subgraph only if it is adjacent to every vertex that is already in the subgraph, and discarded otherwise. The process is repeated until there are no more vertices that can be added to the subgraph. For further exploration, consider learning about the Bron-Kerbosch algorithm, which is a method to find all maximal cliques in an undirected graph. Also learn about an algorithm that can be used to find only the cliques of a specific size k in the graph.

Learn about minimum spanning trees and their applications. Then understand the Kruskal's Minimum Spanning Tree Algorithm, which is a greedy algorithm used to find the minimum spanning tree in a connected weighted graph. It works by adding increasing cost edges that connect disconnected trees until a spanning tree is formed.

Learn about mathematical greedy algorithms which involve using a greedy approach to solve mathematical problems. Examples include the Egyptian Fraction Problem, Split Number into K parts with Maximum GCD, Make Elements Equal, and Maximum Perimeter of Triangle. In these problems, the greedy approach involves iteratively selecting the best possible option that satisfies certain mathematical constraints.

Egyptian Fraction Problem involves representing a positive fraction as a sum of unit fractions, i.e., fractions with a numerator of 1. The solution uses a greedy algorithm approach. The algorithm involves iteratively extracting the largest unit fraction and subtracting it until the remaining fraction becomes a unit fraction. The original fraction can then be represented as the sum of all extracted unit fractions.

Split Number into K Parts such that GCD is Maximum problem involves splitting a given number into K parts such that their greatest common divisor (GCD) is maximum. The first approach calculates the minimum possible sum of K unique numbers and checks if the given number can be split into K unique numbers. It then finds the first number that can divide the given number and returns its quotient as the maximum GCD. The greedy approach uses the property of complementary numbers to find the divisors of the given number, checks if they have K elements, and returns the maximum GCD.

Learn how to find the minimum number of operations to make all elements of an array equal by finding the minimum element in the array as the target value, and then for each element in the array, calculate the amount of decrement operations required to reach the target value. The sum of all these operations gives the minimum number of operations required to make all elements of the array equal.

Maximum Perimeter of a Triangle problem involves finding the maximum possible perimeter of a triangle, given an array of integers representing the lengths of line segments. In the greedy approach, the sides of the triangle are first sorted in increasing order, and then a loop starts from the last element. For each element, if the sum of the two previous elements is greater than the current element, the three sides are outputted as the result and the loop is broken. If no such triplet is found, the output is -1.

Learn about other greedy problems that involve a common approach of iteratively making locally optimal decisions to arrive at a globally optimal solution. These problems include Fitting Shelves Problem, Huffman Encoding, Minimum Sum of Product of Two Arrays, Jump Game II, and many more.

Fitting Shelves Problem involves fitting shelves of different lengths on a wall of fixed length, optimizing for minimum waste space. Given a wall of length W and two shelves of lengths m and n, the task is to find the minimum empty space on the wall after placing the maximum number of shelves on it. The brute force method involves trying every combination of the number of shelves, while the greedy algorithm tries to minimize the empty space by maximizing the use of larger shelves before using smaller ones.

Huffman Encoding is a lossless data compression algorithm that assigns variable-length codes to characters based on their frequency of occurrence in a message. Lossless compression is a type of data compression in which no information is lost during the compression process. The greedy approach of Huffman algorithm involves creating a min heap of leaf nodes with each character and its frequency, and repeatedly combining the two nodes with the smallest frequency into a new internal node with a sum of their frequencies, until only one node remains. The codes for each character are then printed by traversing the tree and appending a "0" or "1" to the code at each left or right turn, respectively. For a deeper dive into data compression algorithms, explore the Fano-Shannon algorithm.

Minimum Sum of Product of Two Arrays problem uses a greedy approach to minimize the sum of the product of two arrays by sorting the arrays in ascending and descending orders. This allows for multiplying the smallest number of one array with the largest number of the other array. The approach involves multiplying each pair from both arrays and adding the results to get the sum. The brute force approach involves calculating all possible combinations of pairs, computing the sum of products for each combination, and choosing the one with the minimum sum.

Jump Game II is the problem of finding the minimum number of jumps needed to reach the end of an array, where each element represents the maximum number of steps that can be taken from that position. A few approaches discussed use the concepts of dynamic programming and finding the nth Fibonacci number. The first approach uses recursion to solve the problem by exploring all branches in a recursion tree and returning the minimum number of jumps to reach the last index. The second approach involves using dynamic programming to optimize the recursive solution by storing results of subproblems in an array to eliminate repeated work. The third approach is a top-down dynamic programming approach where solutions to smaller subproblems are found recursively and cached in an auxiliary array to be used for subsequent computations. The greedy approach makes an optimal choice at each step by determining the next steps that will push the index closer to the last index.

Smallest Palindrome Greater Than N With Same Digits involves finding the smallest palindrome greater than a given number N using the same digits as N. The naive approach suggests generating all possible permutations of a number to find the next palindrome greater than N, but this can be computationally expensive if N is very large. The greedy approach involves checking if the given number N is already a palindrome, and if not, determining if a palindrome is possible by checking the frequency of characters. For odd-length strings, the character occurring an odd number of times is placed in the middle, and for even-length strings, the characters are placed symmetrically around the middle. The algorithm then returns the smallest possible palindrome greater than N.

Closest String with No Same Consecutive Character is a problem of finding the closest string without any consecutive identical characters. The solution is a simple greedy approach that involves iterating through the input string, and if two consecutive characters are found to be the same, the current character is changed to its previous character.

Split N into Maximum Composite Numbers problem employs an algorithm to split a given number N into a maximum number of composite numbers, by checking all possible splits and selecting the one with the maximum number of composite numbers. To maximize the number of composite numbers in a given number n, a greedy approach is used by dividing n by 4 and subtracting a certain number based on the remainder, either 9, 6, or 15, to make it perfectly divisible by 4.

Largest Lexicographic Array with at most K Consecutive Swaps challenge uses an algorithm to find the lexicographically largest permutation of an array with at most K consecutive swaps allowed. The naive approach involves generating all permutations. A better, greedy approach involves looping through the array and swapping each element with the largest element that can be swapped with it in at most K swaps until either K swaps have been made or the array is lexicographically largest.

Minimum Product Subset of an Array problem utilizes an algorithm to find the minimum product subset of an array, i.e., the subset of elements whose product is minimum among all possible subsets. The naive approach generates all subsets of the array, whereas the greedy approach uses observations based on the number of negative numbers, zeros, and positive numbers in the array to determine the minimum product subset.

Learn how to find the maximum product subset of an array using a greedy algorithm to find the maximum product subset of an array, i.e., the subset of elements whose product is maximum among all possible subsets. The naive approach involves generating all subsets and calculating the product for each of them. The greedy approach is based on the number of negative numbers, zeros, and positive numbers in the array. Specifically, the approach considers four cases: odd number of negative numbers, even number of negative numbers, zeros and no positive numbers, and all numbers negative.

Learn how to find the largest palindromic number that can be formed by rearranging the digits of a given number N. The brute force approach involves finding all palindromic permutations of the digits, while the greedy approach counts the occurrences of each digit and rearranges them in a specific order to obtain the largest palindrome.