There are four problems on the final.Note: Recall that there is no collaboration on the final.Problem 8.1. A hospital is trying to schedule their doctors for night shifts over the next nnights. There are d doctors. Each doctor i can only work certain nights Pi due to personalconstraints. For night k, the hospital needs exactly sk doctors to do the night shift. To befair, the hospital doesn’t want any doctor to do more than m night shifts.Give a polynomial-time algorithm to determine whether the hospital can schedule theirdoctors so that all the constraints are met. If the hospital can, your algorithm should alsooutput for each doctor the list of its night shifts.Problem 8.2. Let M2C be the following problem. Given a 2CNF formula φ and an integerk, decide if φ has a satisfying assignment with at least k variables set to true. In other words:M2C = {(φ, k) : φ is a 2CNF which has a satisying assignment with ≥ k variables true}.For example, consider φ = (x ∨ y) ∧ (y ∨ z). We have that (φ, 2) ∈ M2C becauseyou can set x and y to true and z to false, but (φ, 3) 6∈ M2C.Give a polynomial-time reduction from CLIQUE to M2C. Prove that the reduction iscorrect.(Hint: It may be useful to notice that a set of nodes C is a clique if and only if for every{i, j} which is not an edge, at least one of i and j is not in C.)Problem 8.3. For your co-op you are developing the next state-of-the-art flight searchengine. You have the list of all n daily flights in the world. For each flight you have startingcity, destination city, departure time, arrival time, and price. (The arrival time is alwaysafter the departure time.) A customer currently at city cs wants to get to city cd. It is nowtime ct.1. Describe an algorithm to compute the earliest possible time the customer can arriveat destination, using any number of flights and at any cost.2. Same as 1., but now the customer won’t pay more than cp in total for the trip.3. Same as 2., but in addition the customer won’t do more than cf flights. (Note youhave both a constraint on the price and on the number of flights.)Your running time should be polynomial in n.Problem 8.4. Starting with an empty AA tree, you do the following operations in order:insert(3), insert(5), insert(1), insert(2), insert(7), insert(8), insert(6), insert(4), delete(2),delete(6). Draw the tree after each insertion and deletion, including the levels of the nodes.(Note that insertion and deletion call other functions. You are only required to draw the treeat the end of insertion and deletion; but feel free to draw intermediate trees for convenience.)60本团队核心人员组成主要包括BAT一线工程师，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写编程、代写程序、代写留学生程序作业语言或工具包括但不限于以下范围:C/C++/C#代写Java代写IT代写Python代写辅导编程作业Matlab代写Haskell代写Processing代写Linux环境搭建Rust代写Data Structure Assginment 数据结构代写MIPS代写Machine Learning 作业 代写Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导Web开发、网站开发、网站作业ASP.NET网站开发Finance Insurace Statistics统计、回归、迭代Prolog代写Computer Computational method代做因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp
网友评论