关键词 >
CS260 Algorithms
发布时间：2023-04-21
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computer Science
CS260
Algorithms
STUDENT INSTRUCTIONS
1. Read all instructions carefully. We recommend you read through the entire paper at least once before writing.
2. There are 5 questions. All candidates should attempt 1 question in Section A and 2 questions in Section B.
3. You should not submit answers to more than the required number of questions.
4. You should handwrite your answers either with paper and pen or using an electronic device with a stylus (unless you have special arrangements for exams which allow the use of a computer). Start each question on a new page and clearly mark each page with the page number, your student id and the question number.
Handwritten notes must be scanned or photographed and all individual solutions collated into a single PDF with pages in the correct order.
5. Please ensure that all your handwritten answers are written legibly, preferably in dark blue or black ink. If you use a pencil ensure that it is not too faint to be captured by a scan or photograph.
6. Please check for legibility before uploading. It is your responsibility to ensure your work can be read.
7. Add your student number to all uploaded files.
8. You are permitted to access module materials, notes, resources, references and the internet during the online assessment.
9. You must not communicate with any other candidate during the assessment period or seek assistance from anyone else in completing your answers. The Computer Science Department expects the conduct of all students taking this assessment to conform to the stated requirements. Measures will be in operation to check for possible misconduct. These will include the use of similarity detection tools and the right to require live interviews with selected students following the assessment.
10. By starting this assessment, you are declaring yourself fit to undertake it. You are expected to make a reasonable attempt at the assessment by answering the questions in the paper.
IMPORTANT INFORMATION
We strongly recommend you use Google Chrome or Mozilla Firefox to access the Alternative Exams Portal.
You are granted an additional 45 minutes beyond the stated duration of this assessment to allow for downloading/uploading your assessment, your files and any technical delays.
Students with approved Alternative Exam Arrangements (Reasonable Adjustments) that permit extra time and/or rest breaks will have this time added on to the stated duration.
You must have completed and uploaded the assessment before the 24-hour assessment window closes.
Late submissions are not accepted.
If you are unable to submit your assessment, you must submit Mitigating Circumstances immediately, attaching supporting evidence and your assessment. The Mitigating Circumstances Panel will consider the case and make a recommendation based on the evidence to the Board of Examiners.
SUPPORT DURING THE ASSESSMENT
Operational Support
● Use the Alternative Exams Portal to seek advice immediately if during the assessment period:
O you cannot access the online assessment
O you believe you have been given access to the wrong online assessment
Operational support will be available between 09:00 and 17:00 BST for each examination (excluding Sunday)
Technical Support
● If you experience any technical difficulties with the Alternative Exam Portal please contact helpdesk@warwick.ac.uk
Technical support will be available between 09:00 and 17:00 BST for each examination (excluding Sunday)
Academic Support
● If you have an academic query, contact the invigilator (using the ‘Contact an Invigilator’ tool in AEP) to raise your issue. Please be aware that two-way communication in AEP is not currently possible
Academic support will normally be provided for the duration of the examination (i.e. for a 2 hour exam starting at 09:00 BST, academic support will normally be provided between 09:00 and 11:45 BST). Academic support beyond this time is at the discretion of the department.
Other Support
● if you cannot complete your assessment for the following reasons submit Mitigating Circumstances immediately:
O you lose your internet connection
O your device fails
O you become unwell and are unable to continue
O you are affected by circumstances beyond your control
Section A
Answer ONE question from this section.
1. (a) [4 marks] Let A be a sequence of n numbers A = (A[1], A[2], . . . , A[n]). We say that indices i1 , i2 , . . . , ik are a downtrend of length k in A if 1 s i1 < i2 < . . . < ik s n and A[i1] > A[i2] > . . . > A[ik ].
The downtrend graph of a sequence A = (A[1], A[2], . . . , A[n]) has n vertices 1, 2, . . . , n, and there is a directed edge (i, j) if and only if i < j and A[i] > A[j]. Draw the downtrend graph of the sequence A = (8, 5, 7, 4, 6, 3).
(b) [6 marks] What is the length of the longest downtrend in the sequence A =
(8, 5, 7, 4, 6, 3)?
Give such a longest downtrend and provide its interpretation in the downtrend graph of A.
(c) [12 marks] Design a polynomial-time algorithm that—given a sequence A of n numbers as input—computes the length of a longest downtrend in A. In order to achieve full credit, your algorithm should run in time O(n2 ).
(d) [8 marks] The SQUARE problem is—given an integer x written in binary as input—to compute the binary representation of its square x2 . The MULTIPLY problem is—given two integers y and z written in binary as input—to compute the binary representation of their product yz .
Give a linear-time reduction from MULTIPLY to SQUARE.
Is it possible that squaring is algorithmically easier than multiplication? In other words, can SQUARE be solved asymptotically faster than MULTIPLY?
2. (a) [5 marks] Two closed intervals I1 = [s1 , f1] and I2 = [s2 , f2] are compatible if they do not overlap, that is, if f1 < s2 (I1 finishes before I2 starts) or f2 < s1 (I2 finishes before I1 starts).
Consider five closed intervals I1 = [9, 11], I2 = [2, 10], I3 = [5, 8], I4 = [3, 6], and I5 = [1, 4]. Draw the undirected incompatibility graph of those intervals, in which there is an edge { j, k } if and only if intervals Ij and Ik are not compatible.
(b) [6 marks] Is { 1, 3, 4 } an independent set in the incompatibility graph from
part (a)?
What is the largest independent set in the incompatibility graph from part (a)? Argue that it coincides with the largest set of pairwise compatible intervals.
(c) [6 marks] Is { 1, 3, 4 } a vertex cover in the incompatibility graph from part (a)? What is the smallest vertex cover in the incompatibility graph from part (a)?
(d) [13 marks] The INTERVAL-SCHEDULING decision problem is—given n inter- vals [s1 , f1], [s2 , f2], . . . , [sn , fn] and a number k—to determine if there are k intervals that are pairwise compatible.
Give a polynomial-time reduction from the INTERVAL-SCHEDULING problem to the VERTEX-COVER problem.
Section B
Answer TWO questions from this section.
3. (a) [5 marks] A k -kite is an undirected graph with 2k vertices, in which k vertices (the “body” of the kite) are a clique and the other k vertices form a “tail”—a path with k vertices and k _ 1 edges, and exactly one end of the tail is connected by
one edge to one of the vertices in the body.
Draw a 4-kite.
Then draw a graph with 10 vertices that contains a 3-kite as a subgraph. Make it clear which vertices of the graph form the body and the tail of the kite, respectively.
(b) [8 marks] The KITE decision problem is—given an undirected graph G and a
number k as input—to decide if graph G contains a kite with 2k vertices as a subgraph.
Prove that KITE is in the computational complexity class NP by designing a polynomial-time certifier for the problem.
(c) [10 marks] Prove that KITE is NP-complete. You may assume that the decision problem CLIQUE is NP-complete.
(d) [4 marks] A disjunctive normal form (DNF) formula is a disjunctions of conjunc- tive clauses, where a conjunctive clause is a conjunction of literals.
Give an example of a DNF formula that uses 4 boolean variables, and is a disjunc- tion of 4 conjunctive clauses, each of which is a conjunction of 3 literals.
Is the DNF formula that you have given satisfiable? If yes, give a satisfying as- signment; if not, argue why not.
(e) [8 marks] Design a polynomial-time algorithm that—given a DNF formula as
input—determines if it is satisfiable and outputs a satisfying assignment if the answer is yes.
4. Here, we consider undirected graphs that are undirected rooted trees, represented by a parent array P , such that if a vertex v is the root then P [v] = v, and otherwise P [v] is the parent of v . For example, the following undirected rooted tree T:
is represented by the parent array:
|
Vertex v |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
1 |
1 |
2 |
|
2 |
|
|
1 |
|
1 |
|
|
(a) [4 marks] Two edges {v, u} and {w, z} in an undirected graph are adjacent if
{u, v} n {w, z} 
0. A set of edges is isolated if no two edges in it are adjacent. The size of a set of edges is the number of edges in it.
Are sets { {2, 5}, {8, 9}, {10, 12} } and { {10, 12}, {5, 7}, {1, 10} } of edges in the example tree T above isolated?
Give an isolated set of edges of size 4 in T.
(b) [4 marks] What is the largest size of an isolated set of edges in the example tree T
above?
Give such a set of edges of the largest size.
(c) [10 marks] Design a polynomial-time algorithm that—given an undirected rooted tree as input—computes the largest size of an isolated set of edges in the tree. In order to achieve maximum credit, your algorithm should have linear running time; partial credit can be given for slower algorithms.
(d) [7 marks] Draw the tree S with weighted vertices represented by the following
parent array:
|
Vertex v |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
Parent P [v] of v |
1 |
1 |
2 |
2 |
1 |
5 |
1 |
7 |
7 |
|
Weight W [v] of v |
3 |
4 |
1 |
2 |
1 |
2 |
5 |
1 |
1 |
Give an independent set in S of largest size.
The total weight of a set of vertices is the sum of the corresponding weights. Give an independent set in S that has largest total weight.
(e) [10 marks] Design a polynomial-time algorithm that—given a tree with weighted
vertices as input—computes the largest total weight of an independent set in the tree.
5. (a) [4 marks] Two sequences X = (x1 , x2 , . . . , xn ) and Y = (y1 , y2 , . . . , ym ) have a joint segment of length k that ends at positions (i, j) if:
(xi −k+1, xi −k+2 , . . . , xi ) = (yj −k+1, yj −k+2 , . . . , yj ) .
For example, sequences X = (4, 2, 2, 4, 2, 2, 4, 2, 4) and Y = (4, 2, 4, 2, 2, 4, 4, 2) have a joint segment (x8 , x9 ) = (y5 , y6 ) = (2, 4) of length 2 that ends at positions (9, 6). What is the longest joint segment of X and Y that ends at positions (4, 3)? What is the longest joint segment of X and Y that ends at positions (6, 5)?
(b) [6 marks] What is the largest length of a joint segment of sequences X and Y
from part (a)?
Give positions (i, j) at which such a longest joint segment ends.
(c) [10 marks] Design an algorithm that—given sequences X = (x1 , x2 , . . . , xn ) and Y = (y1 , y2 , . . . , ym ) as input—computes the largest length of their joint segment. In order to achieve substantial credit, your algorithm should run in time O(nm).
(d) [15 marks] The EXACT-SPANNING-TREE decision problem is—given an undi- rected graph G = (V, E), with an edge weight W [e] for each edge e e E, and a number B, as inputs—to determine if there is a spanning tree of G whose total weight is exactly B .
Prove that the EXACT-SPANNING-TREE problem is NP-complete. Hint. You may assume that the SUBSET-SUM problem is NP-complete.
