CSE221-Lab Assignment 05 Solved

Problem Descriptions:

The following tasks need to be solved using Greedy Algorithm Strategy. Greedy is an algorithm design strategy used in optimization problems where the next available choice with maximum benefit is chosen in each step to reach the final optimal solution. You have learned several greedy algorithms such as dijkstra’s shortest path, prim’s and kruskal’s MST, fractional knapsack, interval scheduling, huffman coding etc. The problems below are related or similar to some of the greedy algorithms you learned in class. Read the task descriptions carefully and implement the algorithm using either Java or Python. The output format MUST match exactly as shown in each task.

Task 1 

Suppose, you have N number of assignments with their time intervals- i.e. starting and ending times. As you are a student, you need to find out how you can finish the maximum number of assignments. Now, Implement a greedy algorithm to find the maximum number of assignments that can be completed by you.The following conditions must be met when writing the code: A student can only work on a single assignment at a time.

The input will contain N assignments, and then N lines with the starting time and ending time in the format given below:

N

S₁ E₁

S₂ E₂

…….

S𝑛 E𝑛

You have to read input from a file. The output will contain the maximum number of assignments that can be completed followed by  the intervals of the selected assignment. Sample input and output is given below.  Name your input file

“task1_input.txt”. Make sure to try out different input examples to ensure that your code is working for different cases. Include the input file in your zipped submission folder.

Input 1:

7

0 4

3 4

1 5

9 10

6 9

2 3

1 2
Input 2:

6

1 5

1  2

2  4

6 8

5 7

8 9
Output 1:

5

1  2

2  3

3  4

6 9

9 10
Output 2:

4

1  2

2  4

5 7

8 9
A  greedy algorithm for the above problem is discussed below. Before you look at the algorithm it is recommended that you spend some time and try to think of a solution yourself.

//arr[ ][ ] is a 2D array-each index contains the start and finish time of each assignment

Assignment_Selection (arr[ ][ ], n)

1.    Sort the assignments in ascending order based on ending time in the array, arr

2.    Add the 1st assignment from the sorted array in a queue/list “selected”

3.    initialize a variable count = 1.

4.    Current finish time f = arr[0][1] //(finish time of first assignment)

5.    For each remaining assignment in index c:

a. If the starting time of this assignment is greater or equal to the ending time of previously selected assignment, f

i.           then count++

ii.          f=arr[c][1]

iii.         Add the start and finish time of assignment in index c to “selected”

6.    Print count.

7.    Print the queue/list selected

Task 2 

Maximum number of activities from a total of N activities need to be completed within a day. Each activity has a time interval- i.e. a start and a finish time. The activities can be distributed between M people. Implement a greedy algorithm to find the total number of activities that can be completed by M people. The following conditions must be met when writing the code:

1.    One person cannot do activities with overlapping time intervals, so each person can do only one activity at a given time interval.

2.    Each activity can be completed by only one person.

For task 2 the pseudocode is not provided. You have to modify the pseudocode from Task 1 to complete Task 2.

The input will contain N and M, and then N lines with the start time and finish time in the format given below:

N M

S₁ F₁ S₂ F₂

…….

S𝑛 F𝑛

You have to read input from a file. The output will contain the total number of activities that can be completed. Sample input and output is given below.  Name your input file “task2_input.txt”. Make sure to try out different input examples to ensure that your code is working for different cases. Include the input file in your zipped submission folder.

Input 1:

5 2

1 5

3 6
Input 2:

3 2

3 6

2 4
2 5

8 10

6 9
2 3
Output 1: 4
Output 2: 3
Task 3 

Jack and Jill’s parents decide to make their children do some house chores. So they list a set of activities that can be completed in a whole day. In order to complete each activity a certain amount of time (in hours) is required. The parents randomly call each of their children several times separately to choose from the given activities. In each call the children choose an activity based on the following conditions:

1.    In each call, each of them chooses one activity

2.    Jack has to choose an activity that has not been selected yet.

3.    Jill, being very little, should choose an activity that Jack has already chosen so that she can help her older brother because she cannot do such tasks by herself.

4.    Jack does not like doing chores, so he decides he would choose the activity that requires the shortest amount of time to complete among the remaining activities.

5.    Jill really adores her brother and wants to help him out the most she can, so in each call she decides to choose the activity that needs the maximum time to complete out of the activities chosen by Jack so far.

Implement a greedy algorithm that will meet all above conditions. The input will be Nthe number of tasks, followed by a sequence of N numbers denoting the time it takes to complete each task and then a call string which is a string of characters only containing J or j representing who is called next Jack (J) or Jill (j). The input format will be:

N

T T …… T

JJjJjjJ₁       ₂  𝑛

Assume that both the children will be called and Jack will be called either the same or greater number of times than Jill. You should output the sequence of tasks chosen and the total hours each of the children will be working. Sample input output is given below. You should read from a file. Name the file “task3_input.txt” and include it in the submission folder. Sample input output is given below:

Input 1:-

4

1 4 2 3

JJjJjjJ
Input 2:-

3

2 5 3

JjJJjj
Output1:-

1223314

Jack will work for 10 hours

Jill will work for 6 hours
Output 2:

223553

Jack will work for 10 hours

Jill will work for 10 hours
A possible greedy algorithm for the above problem is discussed below. Before you look at the algorithm it is recommended that you spend some time and try to think of a solution yourself.

1. Sort the activities in ascending order of time in an array 2. Create a stack or priority queue for Jack’s current chosen task.

3.    Initialize index to 0.

4.    Create variables for sequence, Jack’s hours and Jill’s hours

5.    For each character c in the call string

a.    If (c==”J”)

i.           Push value of the index of sorted array in the stack/priority queue

ii.         Append the value in the sequence

iii.        Increment index iv.  Add the value to Jack’s hours

b.    else if  (c==”j”)

i.           Pop the top of the stack or highest value from priority queue

ii.         Append the popped value in the sequence

iii.        Add the popped value to Jill’s hours

6.    Print sequence, Jack’s hours and Jill’s hours