Lab Assignment - 05

Submission Link: https://forms.gle/tRqcyhFZbPhrChsa6

Submission Guidelines:
1. You can code all of them either in Python or Java. But you should choose 1
language for all tasks.
2. For each task write separate python files like task1.py, task2.py and so on.
3. For each task include the input files(if any) in the submission folder.
4. All files (input and code) MUST be put in a folder. The folder MUST be named
following the format sec_ID_labNo. Zip this folder. This will result in a zip format
of sec_ID_labNo.zip. (Example: 2_20101234_1.zip). Submit this zip in the
above mentioned submission link.
5. You MUST follow all the guidelines, naming/file/zipping convention stated above.
Failure to follow instructions will result in straight 50% mark deduction.

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₂
…….
Sn En

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: Input 2:
7 6
04 15
34 12
15 24
9 10 68
69 57
23 89
12

Output 1: Output 2:
5 4
12 12
23 24
34 57
69 89
9 10

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:

NM
S₁ F₁
S₂ F₂
…….
Sn Fn

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: Input 2:
52 32
15 36
36 24
25 23
8 10
69

Output 1: Output 2:
4 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 N-
the 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₂…… Tn
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:- Input 2:-
4 3
1423 253
JjJJjj
JJjJjjJ

Output1:- Output 2:
1223314 223553
Jack will work for 10 hours Jack will work for 10 hours
Jill will work for 10 hours
Jill will work for 6 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