Activity Selection Problem Analysis

Definition: Scheduling a resource among several competing activities.
Goal: To select a maximum-size set of mutually compatible activities.

For example consider the following problem:

Rules to Select the items are:
1. Sort the activities according to thier finish time.
2. Select the first item from the Sorted list.
3. Then for rest of the activities select the items if
Start Time of the current activity > = Finish Time of the previous activity.

So if we sort the activities according to their finish time (rule 1) it becomes like below:

Now for the first item select the first activity from above list (rule 2). So, activity A1.

Now the current activity is A2 and its Start time 3 > = finish time of prevoius activity is 2. So, A2 is also selected.

Now the current activity is A1 and its Start time 0 < = finish time of prevoius activity is 4. So, A1 is will not be selected.

Now the current activity is A5 and its Start time 5 > = finish time of prevoius activity is 4 (last selected item). So, A5 is also selected.

Now the current activity is A4 and its Start time 5 < = finish time of prevoius activity is 7 (last selected item). So, A4 will not be selected.

Now the current activity is A6 and its Start time 8 > = finish time of prevoius activity is 7 (last selected item). So, A6 is also selected.

So, the selected activities will be:
A3 , A2, A5, A6

To see the python implementation of the above algorithm click here

Comments

DFS Performance Measurement

Completeness DFS is not complete, to convince yourself consider that our search start expanding the left subtree of the root for so long path (maybe infinite) when different choice near the root could lead to a solution, now suppose that the left subtree of the root has no solution, and it is unbounded, then the search will continue going deep infinitely, in this case , we say that DFS is not complete. Optimality Consider the scenario that there is more than one goal node, and our search decided to first expand the left subtree of the root where there is a solution at a very deep level of this left subtree , in the same time the right subtree of the root has a solution near the root, here comes the non-optimality of DFS that it is not guaranteed that the first goal to find is the optimal one, so we conclude that DFS is not optimal. Time Complexity Consider a state space that is identical to that of BFS, with branching factor b, and we start the search fro...

Regularization in Deep Learning / Machine Learning - Prevent Overfitting

image source: mlexplained Overfittng happens in every machine learning (ML) problem. Learning how to deal with overfitting is essential to mastering machine learning. The fundamental issue in machine learning is the tension between optimization and generalization. Optimization refers to the process of adjusting a model to get the best performance possible on the training data (the learning in machine learning ), whereas generalization refers to how well the trained model performs on data it has never seen before . The goal of the game is to get good generalization, of course, but you don’t control generalization; you can only adjust the model based on its training data. The processing of fighting overfitting is a way called regularization . [1]. How do you know whether a model is overfitting? The best initial method is to measure error on a training and test set. If you see a low error on the training set and...

Soumik's Tech Blog

Search This Blog