Month: November 2024

Day 29: Building a Small Project – Implementing What You’ve Learned

Now that you’ve learned the basics of data structures and algorithms, it’s time to put your knowledge into practice! Consider building a Task Manager application where tasks have dependencies (represented as a graph) and the order of completion is determined using DFS or BFS.

Day 28: Week Review and Practice – Strengthen Your Understanding with Challenges

This week, you’ve learned about graphs, graph traversal algorithms, dynamic programming, and greedy algorithms. To solidify your knowledge, try solving some practice problems like:

• Implement DFS and BFS on a graph of your own design.
• Solve Fibonacci, Coin Change, and LIS problems using dynamic programming.
• Try out the Activity Selection problem or Huffman Coding.

Day 27: Greedy Algorithms – Optimal Solutions with Simple Approaches

Greedy algorithms are designed to make the optimal choice at each step, aiming for an overall optimal solution.

Activity Selection Problem (Greedy Approach)

javaCopy codeimport java.util.*;

public class ActivitySelection {
    public static List<Integer> selectActivities(int[] start, int[] finish) {
        int n = start.length;
        List<Integer> selectedActivities = new ArrayList<>();
        
        // Sort activities based on their finish time
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (i, j) -> finish[i] - finish[j]);

        int lastFinishTime = -1;
        for (int i : indices) {
            if (start[i] >= lastFinishTime) {
                selectedActivities.add(i);
                lastFinishTime = finish[i];
            }
        }
        return selectedActivities;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        List<Integer> selectedActivities = selectActivities(start, finish);
        System.out.println("Selected activities: " + selectedActivities);
    }
}

Day 26: Common Dynamic Programming Problems – Step-by-Step Solutions

Let’s explore two classic dynamic programming problems: Coin Change and Longest Increasing Subsequence (LIS).

1. Coin Change Problem

The goal is to find the minimum number of coins required to make a given amount.

javaCopy codepublic class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println("Minimum coins for amount 11: " + coinChange(coins, 11));
    }
}

2. Longest Increasing Subsequence (LIS)

Find the longest subsequence in an array where the elements are in strictly increasing order.

javaCopy codepublic class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println("Length of LIS: " + lengthOfLIS(nums));
    }
}