$35.00
Description
Please submit this assignment via GradeScope at https://gradescope.com . Be sure to identify everyone in your group if you’re making a group submission. (Reminder: groups can include a maximum of three students; we strongly encourage groups of two.)
Remember that this assignment is based on the collected quizzes and quiz solutions. You will likely want to refer to those where you need more details on assignment questions.
Submit by the deadline Monday 5 Mar at 10PM. For credit, your group must make a single submission via one group member’s account, marking all other group members and the pages associated with each problem in that submission using GradeScope’s interface . Your group’s submission must:

Be on time.

Consist of a single, clearly legible le uploadable to GradeScope with clearly indicated solutions to the problems. (PDFs produced via LAT_{E}X, Word, Google Docs, or other editing software work well. Scanned documents will likely work well. Highquality photographs are OK if we agree they’re legible.)

Include prominent numbering that corresponds to the numbering used in this assignment handout (not the individual quizzes). Put these in order starting each problem on a new page, ideally. If not, very clearly and prominently indicate which problem is answered where!

Include at the start of the document the ugrad.cs.ubc.ca email addresses of each member of your team. (Please do NOT include your name on the assignment, however.^{1})

Include at the start of the document the statement: “All group members have read and followed the guidelines for academic conduct in CPSC 320. As part of those rules, when collaborating with anyone outside my group, (1) I and my collaborators took no record but names (and GradeScope information) away, and (2) after a suitable break, my group created the assignment I am submitting without help from anyone other than the course sta.” (Go read those guidelines!)

Include at the start of the document your outsidegroup collaborators’ ugrad.cs.ubc.ca IDs, but not their names. (Be sure to get those IDs when you collaborate!)

Ol’ McDonald is safer, he hi he hi ho
Here is pseudocode for a correct greedy algorithm that solves the McDonald’s safety committee problem:
define produce_safety_committee(array_of_shifts):

_{S}_{max} = none
# where s(none) = f(none) = – 1
previous_S max
= none
list_current = empty list

If you don’t mind private information being stored outside Canada and want an extra doublecheck on your identity, include your student number rather than your name.
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
all_endpoints = all shift endpoints, sorted in increasing order
for endpoint p in all_endpoints:
let S be the shift to which p belongs
if p is a left endpoint:
set Smax to S if f(S) > f(S max)
#

Shifts starting before f(previous_S max) are already covered.

so we don’t need to worry about covering them.
#
if p < f(previous_S max):
mark S as covered
else:
add S to list_current
else if S is not marked as covered:
previous_S max = Smax
add Smax to the committee
mark all shifts from list_current as covered
list_current = empty list
In this question you will complete a proof of correctness of this algorithm.

^{Let} ^{S}1^{; : : : ; S}k be the set of shifts returned by our algorithm. Assume without loss of generality that
S_{1}; : : : ; S_{k} is sorted by nishing times. We will denote the starting and nishing times of shift S_{j} _{by}
s(S_{j}) and f(S_{j}) respectively. We rst prove that S_{1}; : : : ; S_{k} _{is a valid safety committee, by proving} that:
Fact 1 If S is a shift such that s(S) f(S_{j}), then S overlaps one of S_{1}; : : : ; S_{j}_{.}
Proof : The proof is by induction on j. For j = 1, observe that FILL IN THIS PART.
Suppose now that every shift whose starting point is f(S_{j}) overlaps one of S_{1}; : : : ; S_{j}_{. Consider a} shift S such that s(S) f(S_{j+1}).


If s(S) f(S_{j}) then FILL IN THIS PART.



Otherwise, FILL IN THIS PART. Thus f(S) f(T ), which means that it overlaps with

^{S}j+1.
End Proof

^{Let} ^{T}1^{; : : : ; T}m be the shifts in Because our algorithm returns a
a smallest safety committee, sorted by increasing nishing time.
complete safety committee (select the correct statement):
k < m
k m
k = m
k m
k > m
First we establish that
Fact 2 For j = 1; : : : ; m, f(S_{j}) f(T_{j}).
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
Proof : This is clear for j = 1, because FILL IN THIS PART
Suppose now that it is true for S_{j} and T_{j}, and consider S_{j+1} and T_{j+1}. Let S be the shift with the earliest nishing time amongst those that start after f(S_{j}).
FILL IN THIS PART
Hence f(T_{j+1}) f(S_{j+1}).
End Proof
In order to prove that (select the correct statement)
k < m
k m
k m
k > m
we only need to prove that every shift overlaps an element of S_{1}; : : : ; S_{m}_{. Indeed, if there were a shift} S that does not overlap any of them, then FILL IN THIS PART
This is clearly impossible, since in that case none of T_{1}; : : : ; T_{m} would overlap with S.

Recurrences resolve runtimes


Consider the following sorting algorithm:

define sloth_sort(A, first, last): if A[first] < A[last]:
exchange A[first] and A[last]

if (first + 1
< last):
mid = (last
– first + 1) // 3
# integer division
sloth_sort(A, first
+ mid, last)
# sort last
twothirds
sloth_sort(A,
first, last – mid)
#
sort
first twothirds
sloth_sort(A,
first
+ mid, last)
#
sort
last
twothirds again


Write a recurrence relation that describes the worstcase running time of function sloth_sort in terms of n, where n = last first + 1. You can ignore oors and ceilings.



What is the worst case running time of algorithm sloth_sort ?


Consider now this much less useful algorithm:
define not_useful(A, first, last): if last < first + 4:
x = A[last] – A[first]
else:
x = not_useful(A, first+1, last1) – not_useful(A, first+2, last2)
return x
Write a recurrence relation that describes the worstcase running time of function not_useful in terms of n, where n = last first + 1.
3. Finally, consider the following Python algorithm, which we may see again later this term:
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
def deterministic_select(A, i):
if len(A) < 5:
sorted_A = sorted(A)
return sorted_A[i]
blocks = [ ]
for b in range((len(A)1) // 5 + 1): # That is, the ceiling of len(A)/5 blocks.append(sorted(A[b*5:(b+1)*5]))
medians = [block[len(block)//2] for block in blocks]
median_of_medians = deterministic_select(medians, len(medians) // 2 + 1)

lesser
=
[v
for
v
in
A
if
v
<
median_of_medians]
greater =
[v
for
v
in
A
if
v
>
median_of_medians]
moms
= [v for v in A if v == median_of_medians]
if len(lesser) < i <= len(lesser) + len(moms):
return median_of_medians
elif len(lesser) >= i:
return deterministic_select(lesser, i)
else:
return deterministic_select(greater, i – len(lesser) – len(moms))
Knowing that 0.3 len(A) < len(lesser) < scribes the worstcase running time of function
len(A).
0.7 len(A) , write a recurrence relation that dedeterministic_select in terms of n, where n =

Playing the Blame Game
A distributed computing system composed of n nodes is responsible for ensuring its own integrity against
attempts to subvert the network. To accomplish this, nodes in the system can assess each others’ integrity, which they always do in pairs. A node in such a pair with its integrity intact will correctly assess the node it is paired with to report either “intact” or “subverted”. However, a node that has been subverted may freely report “intact” or “subverted” regardless of the other node’s status.
The goal is for an outside authority to determine which nodes are intact and which are subverted. If n=2 or more nodes have been subverted, then the authority cannot necessarily determine which nodes are
intact using any strategy based on this kind of pairing. However, if more than n=2 nodes are intact, it is
possible to condently determine which are which.
Throughout this problem, we assume that more than n=2 of the nodes are intact. Further, we let one
“round” of pairings be any number of pairings overall as long as each node participates in at most one pairing. (I.e., a round is a matching that may not be perfect.)
ONLY PROBLEM IN THIS PART: Give an algorithm in clear, simple pseudocode that runs in O(lg n) rounds and identies an intact node, and briey but clearly justify the correctness of your algorithm
via clear comments interspersed into the algorithm explaining what it does and why. ( HINT: the quiz problems should lead you in a useful direction!)

Mixed Nets
You’re working on the routing for an anonymization service called a “mixnet” in which a network of computers pass messages through a sequence of handos from one source computer to eventually reach
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
To represent this, you have a weaklyconnected, directed acyclic graph (DAG) G = (V; E) composed of designated source and target vertices s; t 2 V and a set of p > 0 simple paths (along which p messages pass) each of which starts at s, ends at t, and includes at least one vertex in between s and t. The paths are also vertex disjoint besides s and t (i.e., no two paths share any other vertex). There are no other vertices or
edges in the graph. For example, here are two dierent graphs both over the same set of vertices and both with p = 2:
Graph #1 Graph #2
In fact, your mixnet actually involves a single set of computers (with a designated start and target computer) and two entirely separate sets of paths among those computers, as with these two sample graphs. At some point as each message passes along its path among the rst set of paths, it switches to using one of the second set of paths instead (never switching back).
Specically, you have an overall graph G made up of two subgraphs G_{1} and G_{2} _{like those specied in} the previous part, where one subgraph’s vertices is an exact copy of the other’s, i.e., G_{1} = (V_{1}; E_{1}) and G_{2} = (V_{2}; E_{2}), where a vertex v_{1} 2 V_{1} if and only if v_{2} 2 V_{2}. (s_{1} and t_{1} _{are the start and target vertices} in G_{1} and their corresponding vertices s_{2} and t_{2} are the start and target in G_{2}_{.) Each subgraph is based} on its own set of p paths, but p is the same for both. There is also a directed edge (v_{1}; v_{2}) for each vertex v_{1} 2 V_{1} except s_{1} and t_{1} leading from G_{1} to G_{2}. (There is no edge from s_{1} to s_{2} or t_{1} to t_{2}_{.)}
So, for the examples above, the overall graph would include both Graph 1 (with each node subscripted like a_{1}) and Graph 2 (with each node subscripted like a_{2}) plus 4 more edges: (a_{1}; a_{2}); (b_{1}; b_{2}); (c_{1}; c_{2}); (d_{1}; d_{2}).
Your goal is to nd p vertexdisjoint paths in the overall graph that start at s_{1} in G_{1} and end at t_{2} _{in} G_{2}. Thus, no two paths visit the exact same vertex (besides s_{1} and t_{2}_{).} _{Additionally}_{, you want to ensure} that no two paths even visit the same vertex in dierent subgraphs (i.e., no path contains v_{1} _{if any other} ^{path contains} ^{v}2). We call two paths visiting the same vertex but in dierent graphs a “conict”.

In a valid instance of this problem, there is always a path from s_{1} to t_{2}_{. Sketch the key points in a} proof of this fact. (Recall that p > 0.)

In a valid instance of this problem, there is never any path from t_{1} to t_{2}_{. Sketch the key points in a} proof of this fact.

We now add the constraint to a valid instance of this problem that it must have some valid solution. Finish the following solution to this problem via reduction to STP (i.e., SMP with ties allowed).
Let the rst vertex along each of the paths out of s_{1} be v_{1;1}; v_{1;2}; : : : ; v_{1;p}_{. Let the last vertex along each}
of the paths into t_{2} be u_{2;1}; u_{2;2}; : : : ; u_{2;p}. Let the men m_{1}; : : : ; m_{p} be the vertices v_{1;1}; v_{1;2}; : : : ; v_{1;p}_{.}
Let the women w_{1}; : : : ; w_{p} be the vertices u_{2;1}; u_{2;2}; : : : ; u_{2;p}_{.}
Let man m_{i} prefer women w_{j} to woman w_{k} when there is a path from s_{1} through v_{1;i} to u_{2;j} _{which} transitions from G_{1} to G_{2} after a steps (and no such path that transitions after fewer than a steps), there is a path from s_{1} through v_{1;i} to u_{2;k} which transitions from G_{1} to G_{2} after b steps (and no

such path that transitions after fewer than b steps), and
. (Let all women w_{k} _{for}
which there is no path from s_{1} through v_{1;i} to u_{2;j} be tied at the end of m_{i}_{‘s preference list.)}
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
^{Let woman} ^{w}i ^{prefer man} ^{m}j ^{to man} ^{m}k when. . . COMPLETE THIS PART. (Hint: think about an arrangement that in some sense mirrors the previous set of preferences.)
Solve the resulting STP instance to produce the perfect matching S = f(w_{i}; m_{j}); (w_{k}; m_{l}); : : :g.

For each pair (w_{i}; m_{j}), use
, always exploring edges that transition from G_{1} to G_{2}
^{before edges that remain in} ^{G}1, to nd (and add to the solution set of paths) the rst path leading from s_{1} to v_{1;i} and then via some number of edges to u_{2} _{;j} and then to t_{2}_{.}

Prove that since some valid solution exists, then some solution to the STP instance produced by the reduction exists which contains no instabilities (weak or strong).
(This doesn’t complete the proof that the reduction is correct, but it will present all the key insights.)

Cover Charge
In the “minimum edge cover” problem, the input is a simple, undirected, connected graph G = (V; E) with jV j 2, and the output is the smallest possible set E^{0} ^{such that} E^{0} E and for all vertices v 2 V , there _{is an edge} _{fv; ug} _{(which is the same as} _{fu; vg) in} _{E}0. That is, every vertex in the graph is the endpoint of some edge in E^{0}^{.}
A maximum matching in a graph G = (V; E) is the largest set E^{00} ^{such that} E^{00} E and there are no three vertices v_{1}; v_{2}; v_{3} 2 V such that fv_{1}; v_{2}g and fv_{1}; v_{3}g are in E ^{00}^{. That is:} E^{00} ^{“marries o” as many} vertices as possible without having any one vertex “married” to two or more vertices.
In this part, assume you have a connected graph G = (V; E) and a maximum matching for the graph

00.

_{Prove that if} _{jE}00_{j} _{=} ^{jEj+1}_{E}00 is a minimum edge cover. 2 , then

Give an e‑cient, optimal greedy algorithm to nd a minimum edge cover for G = (V; E), given a _{maximum matching in the graph} _{E}00, and briey but clearly justify the correctness of your algorithm via clear comments interspersed into the algorithm explaining what it does and why.

Bonus (OPTIONAL)
Worth 1 bonus point each:

Returning to the problem “Playing the Blame Game”, give a short, extremely clear, and complete proof that if exactly half of the nodes are subverted (assuming an even number of nodes), no strategy whatsoever is guaranteed to nd an intact node.

Returning to the problem “Cover Change”, consider the following greedy algorithm for this problem:
Sort the vertices in increasing order by degree Mark all vertices as uncovered
Let the cover E’ be empty.
While there are vertices remaining, pick the next one v: If v is uncovered:
If there is any neighbour u of v that is uncovered:
Find the uncovered neighbour u of v with lowest degree Add {u, v} to E’ and mark u and v as covered
Else:
Pick an arbitrary edge {u, v}, add it to E’, and mark v as covered
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.
Prove that this algorithm is not optimal by providing a very cleanly drawn and clearly explained counterexample. Your counterexample may not rely for its correctness (as a counterexample) on tiebreaking behaviour in the algorithm.
This work is licensed under a Creative Commons Attribution 4.0 International License. For license purposes, the author is the University of British Columbia.