Ravindra Ranwala's Blog

 Introduction Weighted interval scheduling is a variant of the Interval scheduling problem described under chapter 16 of our CLRS book [1]. If you are not familiar with the Interval scheduling problem, I would encourage you to read that in the book [1], before proceeding with the rest of this article. Recall that in the original problem we are given a set of $n$ activities, each with associated start time $s_i$ and finish time $f_i$. Our objective is to find the maximum subset of non-overlapping activities. Moreover, the problem of finding the maximum subset of compatible activities exhibits the greedy choice property. Now with this information in mind, let’s move on to our new variant.   Problem Statement Exercise 16.1-5 Consider a modification to the activity-selection problem in which each activity $a_i$ has, in addition to start and finish time, a value $v_i$. The objective is no longer to maximize the number of activities scheduled, but instead to maximize the total value...

 First of all, I would like to give a bit of context and explain my motivation behind this article. I have gone through the book [1] and found that the proof of correctness is a bit less informative and making it a bit more hard for a reader to understand on their own. Then I checked some other lecture slides, materials and unfortunately found none of them helpful in understanding the proof easily. The first part of the proof, which is Lemma 16.2 is much better and has some illustrations to assist readers, hence I don’t think it requires more explanation. But the last part which is Lemma 16.3 lacks the required details, hence I thought of adding them here to assist other readers because I don’t want them to spend their time going through the painstaking process which I had when I was first reading the proof. Lemma 16.3 Let $C$ be a given alphabet with frequency $c.freq$ defined for each character $c \in C$. Let $x$ and $y$ be two characters in $C$ with minimum frequency. Let $C^\pr...

Problem Statement The 0-1 knapsack problem is the following. A thief robbing a store finds n items. The $i$ th item is worth $v_i$ dollars and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers. The thief wants to take as valuable a load as possible, but he can carry at most $W$ pounds in his knapsack, for some integer $W$. Which items should he take? We call this the 0-1 knapsack problem because for each item, the thief must either take it or leave it behind; he cannot take a fractional amount of an item or take an item more than once. [1] Now let’s take an exercise from our CLRS book [1]. Exercise 16.2-2  Give a dynamic programming solution to the 0-1 knapsack problem that runs in $O(n \cdot W)$ time, where $n$ is the number of items and $W$ is the maximum weight of items that the thief can put in his knapsack. [1] 0-1 knapsack - Definition  Let $n$ be the number of items, $W$ be the capacity of the knapsack. Let $i$ be the current item being considered, $v_i$ and $w_i$...