辅导CSCI 3110、讲解Python设计、Java，c/c++程序调试 讲解Python程序|讲解SPSS
- 首页 >> C/C++编程 CSCI 3110 Final Exam posted: 7 am ADT 31.07.2020
There are 6 questions on this exam, each worth 6 marks, with 1 bonus mark. They can all
be answered in under half a page each; there is no coding. Your overall mark out 30 of will
be the sum of the marks for your best 5 answers; the bonus cannot raise your mark above
30. You can check the textbook, the scribe notes (some of which were uploaded or updated
yesterday!), the Brightspace page and the rest of the internet but you must work on your
own and all work you submit must be your own! You can an use an automatic
translator if you want, for example, but it is cheating to post or discuss the exam with
classmates or anyone else except Travis before midnight. Signs of collusion or plagiarism
will be reported to FCS as evidence of a possible Academic Integrity Offence. You can email
Travis for clarifications but he will not give hints. Please do not contact the TAs during
the exam. Submit your answers as a single PDF to the “final exam” assignment folder on
Brightspace. Good luck!
1
1. Describe a polynomial-time divide-and-conquer algorithm that, given a tree T with a
weight assigned to each vertex, returns a vertex cover with minimum total weight. For
example, in the tree shown below, the vertex cover with the minimum total weight is
d, f, g, h, i, k — even though the smallest vertex cover is e, g, i. You need not prove
your algorithm correct.
(Hint: Because (e, f) is an edge in the example, any vertex cover includes either e
or f or both. Removing (e, f) splits the tree into two pieces, Te including e and Tf
including f. If you can work out the weight w1 = 6 of the lightest vertex cover of
Te, and the weight w2 = 10 of the lightest vertex cover of Te that includes e, and the
weight w3 = 7 of the lightest vertex cover of Tf , and the weight w4 = 10 of the lightest
vertex cover of Tf that includes f, then the weight of the lightest vertex cover of T is
min(w1 + w4, w2 + w3) = 16. How do you work out w1 and w3? More interestingly,
how do you work out w2 and w4?)
2
2. Recall that for the NP-complete problem Knapsack we are given a sequence S =(w1, p1), . . . ,(wn, pn) of weight-profit pairs, a target T and a capacity C, and asked if
there exists a subsequence S.
For the problem Pockets we are again given a sequence S = (w1, p1), . . . ,(wn, pn) of
weight-profit pairs and a target T but now, instead of a single capacity C, we are given
a sequence C = c1, . . . , cm of capacities. Assume w1 ≥ · · · ≥ wn and c1 ≥ · · · ≥ cm. We
are asked if there exists a subsequence S.
In other words, we have n items and m pockets, each pocket has a capacity, and we
want to put at most one item in each pocket so as to obtain total profit at least T
without overfilling any pocket.
Describe a polynomial-time greedy algorithm for Pockets. For example, if
S = (7, 8),(5, 5),(5, 6),(5, 2),(4, 1),(4, 4)
T = 13
C = 6, 5, 5
then your algorithm should return “yes”, since with S
0 = (5, 5),(5, 6),(4, 4) we obtain
profit 5 + 6 + 4 = 15 without overfilling any pocket (since 5 ≤ 6, 5 ≤ 5 and 4 ≤ 5).
You need not prove your algorithm correct (although looking for a proof is a good way
to catch mistakes anyway).
(Hint: Assuming the pockets are sorted in decreasing order by capacity made it easier
to state the problem, but it’s not the best order for solving it. What should you put
in the smallest pocket?)
3
3. A semi-wildcard in a string is special character representing a non-empty subset of
the normal alphabet, and a string containing a mix of normal characters and semiwildcards
represents the set of all normal strings that can be obtained by replacing
each semi-wildcard by a character from the subset it represents. For example, if the
normal alphabet is {A, B, C, D} and S = BA?C!AD with ? representing {B, D} and !
representing {A, D}, then S represents the set {BABCAAD, BABCDAD, BADCAAD, BADCDAD}.
Describe a polynomial-time dynamic-programming algorithm that, given a string S[1..n]
containing a mix of normal characters and semi-wildcards and a normal string T[1..m],
computes
min{ED(S, T) : S ∈ S}
where ED(S, T) denotes the edit distance between S and T. For example, given S =
BAC!AD as described above and T = BADCAD, your algorithm should return 1, since the
edit distance from either BADCAAD or BADCDAD and BADCAD is 1. Notice that in general
the set of strings represented by S can contain exponentially many strings, so trying
them one by one is not feasible! You need not prove your algorithm correct.
(Hint: This questions isn’t as hard as it sounds at first. Start with the “grid with
diagonal arrows” idea we saw in class and add some more arrows in some rows.)
4. For the problem Fair 3-Colourability we are given a graph G on n vertices and
asked if it is possible to colour exactly n/3 vertices red, exactly n/3 vertices green and
exactly n/3 vertices yellow such that no vertex shares an edge with a vertex of the
same colour. Show that Fair 3-Colorability is NP-complete by both showing it is
in NP and reducing a known NP-complete problem to it.
(Hint: Don’t reduce from 3-Sat again; it’s easier than that.)
5. Describe a polynomial-time algorithm that, given a directed acyclic graph G with a
positive weight assigned to each edge, finds the minimum distance from s to each other
vertex when the length of a path is defined to be the product of the weights along that
path, instead of their sum. Can you find a faster algorithm if all the edge weights are
at least 1? For example, the distances from s to the other vertices are shown in the
graph below. You need not prove your algorithm(s) correct.
(Hint: You can solve this either by modifying algorithms you already know or by
reducing to the problems they solve.)
4
6. Suppose that due to various catastrophes, next semester your professor ends up teaching
both 3110 and 3136 with exactly the same n students in each one; the 2-hour final
exams are scheduled back to back; both exams are in the same room with exactly n
immovable, arbitrarily placed desks; and that room is available only for those 4 hours.
The pandemic is over, so at least your professor doesn’t have to worry about social
distancing, but he still doesn’t want students writing the same exam to be sitting
within two meters of each other. Some of the desks are too close together, so he can’t
have all the students write the same exam at the same time, but he decides to have
some students start with the 3110 exam and others start with the 3136 exam, and
then switch halfway through. However, even this won’t work if, for example, there’s
a triangle of three desks with each one within 2 meters of the other two. Describe
a polynomial-time algorithm that lets your professor check if his idea works with the
room’s seating arrangement.
Bonus (1 mark): What if in the winter semester your poor professor is in the same
situation but with three exams in six hours? What about four exams in eight hours
(perish the thought)?
(Hint: You should be able to find the algorithm for two exams by yourself, but for
three or more, Google “unit disk graph”, where is the standard name for this
problem.)
5
There are 6 questions on this exam, each worth 6 marks, with 1 bonus mark. They can all
be answered in under half a page each; there is no coding. Your overall mark out 30 of will
be the sum of the marks for your best 5 answers; the bonus cannot raise your mark above
30. You can check the textbook, the scribe notes (some of which were uploaded or updated
yesterday!), the Brightspace page and the rest of the internet but you must work on your
own and all work you submit must be your own! You can an use an automatic
translator if you want, for example, but it is cheating to post or discuss the exam with
classmates or anyone else except Travis before midnight. Signs of collusion or plagiarism
will be reported to FCS as evidence of a possible Academic Integrity Offence. You can email
Travis for clarifications but he will not give hints. Please do not contact the TAs during
the exam. Submit your answers as a single PDF to the “final exam” assignment folder on
Brightspace. Good luck!
1
1. Describe a polynomial-time divide-and-conquer algorithm that, given a tree T with a
weight assigned to each vertex, returns a vertex cover with minimum total weight. For
example, in the tree shown below, the vertex cover with the minimum total weight is
d, f, g, h, i, k — even though the smallest vertex cover is e, g, i. You need not prove
your algorithm correct.
(Hint: Because (e, f) is an edge in the example, any vertex cover includes either e
or f or both. Removing (e, f) splits the tree into two pieces, Te including e and Tf
including f. If you can work out the weight w1 = 6 of the lightest vertex cover of
Te, and the weight w2 = 10 of the lightest vertex cover of Te that includes e, and the
weight w3 = 7 of the lightest vertex cover of Tf , and the weight w4 = 10 of the lightest
vertex cover of Tf that includes f, then the weight of the lightest vertex cover of T is
min(w1 + w4, w2 + w3) = 16. How do you work out w1 and w3? More interestingly,
how do you work out w2 and w4?)
2
2. Recall that for the NP-complete problem Knapsack we are given a sequence S =(w1, p1), . . . ,(wn, pn) of weight-profit pairs, a target T and a capacity C, and asked if
there exists a subsequence S.
For the problem Pockets we are again given a sequence S = (w1, p1), . . . ,(wn, pn) of
weight-profit pairs and a target T but now, instead of a single capacity C, we are given
a sequence C = c1, . . . , cm of capacities. Assume w1 ≥ · · · ≥ wn and c1 ≥ · · · ≥ cm. We
are asked if there exists a subsequence S.
In other words, we have n items and m pockets, each pocket has a capacity, and we
want to put at most one item in each pocket so as to obtain total profit at least T
without overfilling any pocket.
Describe a polynomial-time greedy algorithm for Pockets. For example, if
S = (7, 8),(5, 5),(5, 6),(5, 2),(4, 1),(4, 4)
T = 13
C = 6, 5, 5
then your algorithm should return “yes”, since with S
0 = (5, 5),(5, 6),(4, 4) we obtain
profit 5 + 6 + 4 = 15 without overfilling any pocket (since 5 ≤ 6, 5 ≤ 5 and 4 ≤ 5).
You need not prove your algorithm correct (although looking for a proof is a good way
to catch mistakes anyway).
(Hint: Assuming the pockets are sorted in decreasing order by capacity made it easier
to state the problem, but it’s not the best order for solving it. What should you put
in the smallest pocket?)
3
3. A semi-wildcard in a string is special character representing a non-empty subset of
the normal alphabet, and a string containing a mix of normal characters and semiwildcards
represents the set of all normal strings that can be obtained by replacing
each semi-wildcard by a character from the subset it represents. For example, if the
normal alphabet is {A, B, C, D} and S = BA?C!AD with ? representing {B, D} and !
representing {A, D}, then S represents the set {BABCAAD, BABCDAD, BADCAAD, BADCDAD}.
Describe a polynomial-time dynamic-programming algorithm that, given a string S[1..n]
containing a mix of normal characters and semi-wildcards and a normal string T[1..m],
computes
min{ED(S, T) : S ∈ S}
where ED(S, T) denotes the edit distance between S and T. For example, given S =
BAC!AD as described above and T = BADCAD, your algorithm should return 1, since the
edit distance from either BADCAAD or BADCDAD and BADCAD is 1. Notice that in general
the set of strings represented by S can contain exponentially many strings, so trying
them one by one is not feasible! You need not prove your algorithm correct.
(Hint: This questions isn’t as hard as it sounds at first. Start with the “grid with
diagonal arrows” idea we saw in class and add some more arrows in some rows.)
4. For the problem Fair 3-Colourability we are given a graph G on n vertices and
asked if it is possible to colour exactly n/3 vertices red, exactly n/3 vertices green and
exactly n/3 vertices yellow such that no vertex shares an edge with a vertex of the
same colour. Show that Fair 3-Colorability is NP-complete by both showing it is
in NP and reducing a known NP-complete problem to it.
(Hint: Don’t reduce from 3-Sat again; it’s easier than that.)
5. Describe a polynomial-time algorithm that, given a directed acyclic graph G with a
positive weight assigned to each edge, finds the minimum distance from s to each other
vertex when the length of a path is defined to be the product of the weights along that
path, instead of their sum. Can you find a faster algorithm if all the edge weights are
at least 1? For example, the distances from s to the other vertices are shown in the
graph below. You need not prove your algorithm(s) correct.
(Hint: You can solve this either by modifying algorithms you already know or by
reducing to the problems they solve.)
4
6. Suppose that due to various catastrophes, next semester your professor ends up teaching
both 3110 and 3136 with exactly the same n students in each one; the 2-hour final
exams are scheduled back to back; both exams are in the same room with exactly n
immovable, arbitrarily placed desks; and that room is available only for those 4 hours.
The pandemic is over, so at least your professor doesn’t have to worry about social
distancing, but he still doesn’t want students writing the same exam to be sitting
within two meters of each other. Some of the desks are too close together, so he can’t
have all the students write the same exam at the same time, but he decides to have
some students start with the 3110 exam and others start with the 3136 exam, and
then switch halfway through. However, even this won’t work if, for example, there’s
a triangle of three desks with each one within 2 meters of the other two. Describe
a polynomial-time algorithm that lets your professor check if his idea works with the
room’s seating arrangement.
Bonus (1 mark): What if in the winter semester your poor professor is in the same
situation but with three exams in six hours? What about four exams in eight hours
(perish the thought)?
(Hint: You should be able to find the algorithm for two exams by yourself, but for
three or more, Google “unit disk graph”, where is the standard name for this
problem.)
5