CSC373 Assignment 3
Network | 代做network | Algorithm | 作业assignment – 这是一个关于计算机网络的题目, 主要考察了关于网络Algorithm的内容,是一个比较经典的题目, 是比较有代表性的Network/network/Algorithm等代写方向, 这个项目是assignment代写的代写题目
Due Monday, 2023 Mar 20, 23:59 p.m. EST
Please make sure you only submit one file to MarkUs
Q1 [10 Points] network Flow
- Each exam has a date and a time, where time is one of morning, afternoon or evening. Each combination of dates and times (eg. the morning of April 14) is called an examination period.
- Each CPO has a list of examination periods when the CPO is available. CPOs cannot be assigned to slots when they are not available.
- Each CPO has a maximum number of exam periods that the CPO can invigilate, which is less than or equal to the number of periods when the CPO is free.
- Each CPO can invigilate at most two exams on a single day.
- If an examination period haslexams, there should be 1. 1 lCPOs available for that period, in case there are CPOs scheduled who cannot make their shift.
You have been hired by the office to help them assign CPOs to exam periods.
(a)[5 Points] You are provided with a list of thenCPOs and their availabilities, the CPOs work preferences, themexamination slots, and the number of exams in each slot. Design an Algorithm using network flow that either assigns each CPO to examination slots satisfying the constraints listed previously, or reports that an assignment is not possible.
(b)[5 Points] Briefly justify the correctness and runtime of the algorithm designed in the previous part, using properties of network flow.
Q2 [10 Points] Network Flow
A wireless network company has a number of sensorss 1 ,… , sn, each located at coordinates (xi, yi) R^2 on some map. The company would like to make the sensors more reliable by assigning each sensorsia backup setBi{s 1 ,… , sn}{si}so that ifsifails, a sensor inBican be used instead. The company decides that:
1
- Each backup setBimust contain sensors within distance at mostdfromsi.
- Each backup setBimust contain at leastrbackup sensors.
- Every sensorsimust belong at mostbbackup sets.
(a)[5 Points] Given the sensors, their coordinates, and the parametersd, r, bdescribed, design an algorithm using network flow techniques to output the backup sets for each sensor, or reports that choosing backup sets is not possible with the given parameters.
(b)[5 Points] Briefly justify the correctness and runtime of the algorithm designed in the previous part.
Q3 [20 Points] Linear Programming
A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.
- Material 1 has density 2 tons/cubic meter, maximum available amount 40 cubic meters, and revenue$1,000 per cubic meter.
- Material 2 has density 1 ton/cubic meter, maximum available amount 30 cubic meters, and revenue$1,200 per cubic meter.
- Material 3 has density 3 tons/cubic meter, maximum available amount 20 cubic meters, and revenue$12,000 per cubic meter.
(a)[10 Points] Write a linear program that optimizes revenue within the constraints.
(b)[10 Points] Write an equivalent minimization problem to the linear program in part (a).
Q4 [20 Points] Linear Programming
A convex polygonPinR^2 can be specified as the intersection of halfspaces of the formaix+biyci.
(a)[10 Points] Give a linear program that finds a rectangle of maximum perimeter that lies within Pin standard form. (No need to actually solve the LP once you end up stating it)
(b)[10 Points] Give a linear program in standard form that finds a circle of maximum radius that lies withinP. (Hint: recall the formula for shortest distance between a line and a point.)
References
Please write down your references here, including any paper or online resources you consult.