Homework: #4 Solution

Problem 1: (5 points) Class Scheduling:

 

Suppose you have a set of classes to schedule among a large number of lecture halls, where any class can be placed in any lecture hall. Each class cj has a start time sj and finish time fj. We wish to schedule all classes using as few lecture halls as possible. Verbally describe an efficient greedy algorithm to determine which class should use which lecture hall at any given time. What is the running time of your algorithm?

 

Problem 2: (5 points) Road Trip:

 

Suppose you are going on a road trip with friends. Unfortunately, your headlights are broken,

so you can only drive in the daytime. Therefore, on any given day you can drive no more than d miles. You have a map with n different hotels and the distances from your start point to each

hotel x1< x2< ... < xn. Your final destination is the last hotel. Describe an efficient greedy

algorithm that determines which hotels you should stay in if you want to minimize the number of days it takes you to get to your destination. What is the running time of your algorithm?

 

Problem 3: (5 points) Scheduling jobs with penalties:

 

For each 1 ≤ 𝑖     ≤ 𝑛   job 𝑗𝑖     is given by two numbers 𝑑𝑖 and 𝑝𝑖, where 𝑑𝑖 is the deadline and 𝑝𝑖 is the penalty. The length of each job is equal to 1 minute and once the job starts it cannot be stopped until completed. We want to schedule all jobs, but only one job can run at any given

time. If job i does not complete on or before its deadline, we will pay its penalty 𝑝𝑖. Design a greedy algorithm to find a schedule such that all jobs are completed and the sum of all penalties is minimized. What is the running time of your algorithm?

 

 

 

Problem 4: (5 points) CLRS 16.1-2 Activity Selection Last-to-Start

 

Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.

 

Problem 5: (10 points) Activity Selection Last-to-Start Implementation

 

Submit a copy of all your files including the txt files and a README file that explains how to compile and run your code in a ZIP file to TEACH. We will only test execution with an input file named act.txt. 

 

You may use any language you choose to implement the activity selection last-to-start algorithm described in problem 4. Include a verbal description of your algorithm, pseudocode and analysis of the theoretical running time. You do not need to collected experimental running times. 

 

The program should read input from a file named “act.txt”.  The file contains lists of activity sets with number of activities in the set in the first line followed by lines containing the activity number, start time & finish time. 

 

Example act.txt:

 

11

 

1 1 4

 

2 3 5 

 

3 0 6 

 

4 5 7 

 

5 3 9 

 

6 5 9

 

7 6 10

 

8 8 11

 

9 8 12

 

10 2 14

 

11 12 16

 

3 

 

3 1 8

 

2 1 2

 

1 3 9

 

In the above example the first activity set contains 11 activities with activity 1 starting at time 1 and finishing at time 4, activity 2 starting at time 3 and finishing at time 5, etc.. The second activity set contains 3 activities with activity 3 starting at time 1 and finishing at time 8 etc. Note: the activities in the file are not in any sorted order.

 

Your results including the number of activities selected and their order should be outputted to the terminal. For the above example the results are: 

 

Set 1

Number of activities selected = 4

 

Activities: 2 4 8 11 

 

Set 2

Number of activities selected = 2

 

Activities: 2 1