# CS 4104 Homework Assignment 3, data and algorithm

CS 4104
Homework Assignment 3
Given: September 9, 2019 Due: September 20, 2019
General directions. The point value of each problem is shown in [ ]. Each solution must
include all details and an explanation of why the given solution is correct. In particular,
write complete sentences. A correct answer without an explanation is worth
no credit. The completed assignment must be submitted on Canvas as a PDF by 5:00
PM on September 20, 2019. No late homework will be accepted.
Digital preparation of your solutions is mandatory. Use of LATEX is optional, but
Use of LATEX (optional, but encouraged).
• Retrieve this LATEX source file, named homework3.tex, from the course web site.
• Rename the file _solvehw3.tex, For example, for the instructor,
the file name would be heath_solvehw3.tex.
• Use a text editor (such as vi, emacs, or pico) to accomplish the next three steps.
• Uncomment the line
% setboolean{solutions}{True}
in the document preamble by deleting the %.
• Find the line
renewcommand{author}{Lenwood S. Heath}
and replace the instructor’s name with your name.
• Generate a PDF and turn it in on Canvas by 5:00 PM on September 20, 2019.
2 Homework Assignment 3 September 9, 2019
i si fi
1 6.5 1.0
2 0.5 5.2
3 4.0 2.9
4 1.2 1.9
5 4.9 6.0
6 3.0 4.4
Figure 1: Sample instance of Weekly Activity Selection.
[60] 1. Here, we modify the Activity Selection problem from class to a new problem,
Weekly Activity Selection. Again, we want to schedule activities in a room by select-
ing activities from a set S = {a1, a2, . . . , an} of requested activities, each activity ai with
a start time si and a finish time fi. However, we want to schedule the room for an entire
week (Monday through Sunday, 7 days) in a recurring, circular fashion. In particular, there
may be an activity that starts on Sunday and extends to Monday. So, all times are in the
real interval [0, 7), and we allow some finish times to be strictly before the corresponding
start times. For example, see Figure 1 for an instance that has such activities. A solution
that maximizes the number of activities selected is {a1, a4, a5, a6}.
A. State the Weekly Activity Selection problem in the formal in-
stance/solution format that we use in class. Modify the statement of the
Activity Selection problem sufficiently to capture the circular nature of
Weekly Activity Selection.
B. Design an efficient Weekly-Schedule algorithm to solve the Weekly Activity
Selection problem and give the corresponding pseudocode. Argue
that your algorithm returns an optimal solution.
C. Give the £ asymptotic worst-case time complexity for your algorithm.
-computer science data homework.

The post CS 4104 Homework Assignment 3, data and algorithm appeared first on mynursinghomeworks.