代写CSCI 3110、代做Python设计、Java，c/c++程序调试

日期：2020-08-02 08:03

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