課程名稱︰演算法 課程性質︰電機所選修 課程教師︰陳和麟 開課學院：電機資訊學院 開課系所︰電機所 考試日期（年月日）︰110.1.11 考試時限（分鐘）：180 試題 : Please answer the following questions on the answer sheets provided. Be sure to write your name and student ID on all answer sheets you use. This is a clo- sed book exam. No books, notes, or calculators may be used during the exam wi- th the exception of one double-sided, hand-written A4 note. Read all questions first. You may not request for clarification after 9:40 am. You may assume that all pairwise comparisons additions and multiplications take Θ(1) time. If you want to apply any result or theorem that has been taught in class (including homeworks), you may do sobut you must state the result or the- orem clearly before using it. Problem 1. (15%) Given a connected undirected graph G. A bridge is an edge who- se removal disconnects the graph. 1. (5%) Given a connected undirected graph G and an edge {u,v} in G, design an O(V+E)-time algorithm to determine whether {u,v} is a bridge. 2. (10%) Given a connected undirected graph G, design an O(V(V+E))-time algori- thm to find all bridges. (hint: spanning trees of the graph must have exactly |V|-1 edges.) In problem 2 and 3, there are n visitors v_1, v_2, ..., v_n from other countri- es and m hotels h_1, h_2, ..., h_m that are eligible for quarantine visitors. Each visitor has exactly 3 hotels that he/she is willing to stay in. Problem 2. (10%) Given the capacity (maximum number of visitors allowed) of eve- ry hotel. Design a polynomial-time algorithm that assigns visitors to hotels or reports that no such assginment is possible. (Each visitor must be assigned to one of the 3 hotels that he/she is willing to stay in.) Briefly justify the co- rectness and analyze the running time. Problem 3. (15%) Assume that hotels have no capacity limits. You must choose a set of hotels such that every visitor has a hotel that he/she is willing to st- ay in. The goal is to minimize the number of hotels chosen. Design a 3-approxi- mation algorithm for this problem. Briefly justify the corectness and analyze the running time. Problem 4. (15%) Given an undirected graph G in which all edge costs are disti- nct. Let C be any simple cycle in G. Probe the following statements or give co- unterexamples. 1. (8%) The most expensive edge in C does not belong to the minumum spanning t- ree. 2. (7%) The cheapest edge in C must belong to the minimum spanning tree. For problem 5 and 6, you must either 1. design a polynomial-time algorithm, briefly justify the correctness. or 2. prove that the problem in NP-comple. You must describe the reduction in det- ail and briefly explain the correctness of your reduction. (Hint: One possible reduction is similar to the reduction from HAM. PATH to HAM. CYCLE descrived in class.) You may use the fact that SAT, 3-SAT vertex Cover, Set Cover, Independent Set, Hamiltonian Path, and Hamiltonian Cycle problems are all NP-complete. Also, you do not need to prove that problems 5, 6 are in NP. Problem 5. (15%) Given an undirected G. Each edge has a (possibly negative) ed- ge cost. The problem is to determine whether the graph G has a simple cycle of total cost 0. Problem 6. (15%) Given a directed acyclie graph G. The problem is to determine whether the grapg G has a Hamiltonian path. Problem 7. (15%) Given a graph G=(V,E). Each edge e has a length a_e ≧ 0 and a loading b_e ≧ 0. Given two nodes s and t in G. For any path P from s to t, de- fine the length of the path to be the sum of lengths sum_{e in P} a_e and the loading of the path to be the minimum loading min_{e in P} b_e. Design an O(E+ VlogV) algorithm to find a path from s to t, which minimizes (loading of the path * length of the path). Briefly justify the corectness and analyze the run- ning time. If you cannot manage this problem, find the path which minimize (lo- ading of the path + length of the path) gives a good partial score (please ind- icate clearly if you are only solve for this partial credit). --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.244.210 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1610380823.A.7D2.html