CS 4104 Homework Assignment 3, data and algorithm

/in /by

[ad_1]

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
encouraged. No matter how you prepare your homework, please include your name.
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.
• Enter your solutions where you find the LATEX comments
% PUT YOUR SOLUTION HERE
• 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.

[ad_2]

Source link