CSC373  Assignment 2

CSC373 
Assignment 2

Instructions
1. Typed assignments are preferred (e.g., PDFs created using LaTeX or Word), especially if
your handwriting is possibly illegible or if you do not have access to a good quality scanner.
Either way, you need to submit a single PDF named “hwk2.pdf” on MarkUS at https:
//markus.teach.cs.toronto.edu/2022-05
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross o↵
any written solution) and write “I do not know how to approach this problem.” If you leave
it blank but do not write this or a similar statement, you will receive 10%. This does not
apply to any bonus (sub)questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your
answer is largely irrelevant, you will receive 0 points.
Q1 [20 Points] Gene Alignment
In bioinformatics, a common task involves determining alignment between two genes (represented
as strings over the alphabet ⌃ = {A, C, G, T}). For example, a possible alignment of x = AT GCC
with y = T ACGCA is:
 A T  GCC
T A  CGCA
As you can see, this involves writing both strings in columns so that
the characters of each string appear in order,
each column contains a character from at least one string,
subject to the previous constraint, columns can contain “gaps” (represented as “”).
The score of a possible alignment is specified through a “scoring matrix”  that gives a value for
each possible column in the alignment. In our example, the total score would be equal to:
(, T) + (A, A) + (T, ) + (, C) + (G, G) + (C, C) + (C, A).
Your task is to come up with an ecient algorithm that takes as inputs two strings x, y 2
{A, C, G, T}⇤ with a [5 ⇥ 5] scoring matrix , and that returns the highest possible score for alignment between x and y. (Assume that (, ) = 1, representing the fact that no alignment can
align two gaps together.)
(a) [5 Points] Define the array(s) or table(s) that your solution would compute. Clearly explain
what each entry means, and how you would compute the final answer given all the entries in your
array(s) or table(s).
1
(b) [7 Points] Write a Bellman equation and briefly justify its correctness.
(c) [4 Points] Describe a bottom-up implementation of your Bellman equation, and analyze its
worst-case running time and space complexity.
(d) [4 Points] Now, modify your algorithm to give a way to print the highest-scoring alignment
itself. For this reconstruction of the solution, you may want to define an additional array, although
that is not strictly necessary. Re-analyze the running time and space complexity of the modified
algorithm.
Hint: You may find it useful to read Section 15.4 of the textbook.
Q2 [20 Points] Board Cutting
A sawmill gets orders for di↵erent lengths of boards `1, `2,..., `n. All of the boards have to be
cut from planks, long pieces of wood with a fixed length L, and for technical reasons, the boards
have to be cut in the order they are given. No matter how the planks are cut into boards, there is
usually some amount of waste left over from each plank.
For example, if the board lengths are 2, 4, 1, 5 and L = 7, then we can cut the boards in many
di↵erent ways — some of them are clearly silly:
cut board 2 from one plank, 4 from another, 1 from another, and 5 from a fourth plank
(leaving four waste pieces with lengths 5, 3, 6, 2), or
cut board 2 from one plank, 4 from another, and 1, 5 from a third plank (leaving three waste
pieces with lengths 5, 3, 1), or
cut board 2 from one plank, 4, 1 from another, and 5 from a third plank (leaving three waste
pieces with lengths 5, 2, 2), or
cut boards 2, 4 from one plank, 1 from another, and 5 from a third plank (leaving three waste
pieces with lengths 1, 6, 2), or
cut boards 2, 4 from one plank and 1, 5 from another (leaving two waste pieces of length 1
each), or
cut boards 2, 4, 1 from one plank and 5 from another (leaving only one waste piece of length
2).
Instructions like “cut boards 2, 5 from one plank and 4, 1 from another” are not valid solutions
because they change the order of the boards.
From the point of view of the sawmill, what matters most is not how many planks are used, nor
how much waste is left in total. What matters is that the waste pieces all be the same length, as
much as possible, because this allows those pieces to be reused more easily for other purposes. So
in the example above, the best choice is the second-last (2, 4 together and 1, 5 together) — the last
solution is not quite as good because the lengths of the waste pieces are 0 and 2 (the plank with
no waste is considered to have waste of length 0).
Formally, consider the following “Board Cutting” problem:
Input: Board lengths `1, `2,..., `n and plank length L, where each length is a positive integer,
each `i  L, and the board lengths are not necessarily all distinct.
2
Output: A division of `1, `2,..., `n into groups (`i0+1,..., `i1 ); (`i1+1,..., `i2 ); ... ; (`ik1+1,..., `ik ),
where i0 = 0, ik = n, `ij+1 + `ij+2 + ··· + `ij+1  L for 0  j  k  1 (intuitively: the total length
of each group is no more than the length of one plank), and Pk1
j=0
L  `ij+1  `ij+2  ···  `ij+1 2
is minimized (intuitively: the lengths of the leftover pieces of plank are all as close to each other
as possible).
(a) [4 Points] Define the array(s) or table(s) that your solution would compute. Clearly explain
what each entry means, and how you would compute the final answer given all the entries in your
array(s) or table(s).
(b) [6 Points] Write a Bellman equation and briefly justify its correctness.
(c) [5 Points] Describe a bottom-up implementation of your Bellman equation, and analyze its
worst-case running time and space complexity.
(d) [5 Points] Now, modify your algorithm to output the optimal division itself. You may define
an additional array to do so, in which case, specify its definition clearly. Re-analyze the running
time and space complexity of the modified algorithm.
Q3 [20 Points] Reducing Edge Capacities
(a) [4 Points] Prove or disprove: if N = (V,E) is a network, f ⇤ is a maximum flow in N, e0 2 E is
an edge with f ⇤(e0) = c(e0), and N0 is the same network as N except that c0
(e0) = c(e0)  1, then
the maximum flow f0 in N0 satisfies |f0
| < |f ⇤|.
(b) [12 Points] Write an algorithm that takes a network N = (V,E), maximum flow f ⇤ in N, and
an edge e0 2 E with f ⇤(e0) = c(e0), and that outputs a maximum flow for network N0
, where N0
is the same as N except that c0
(e0) = c(e0)  1.
Provide a brief argument that your algorithm is correct and analyze its time complexity. For full
marks, your algorithm should be as ecient as possible.
(c) [4 Points] Write an algorithm that takes a network N = (V,E) and that outputs a list of all
edges e1,...,ek with the property that if the capacity of any edge in that list is reduced by one
unit, the value of the maximum flow in N is also reduced.
Q4 [20 Points] Matrix Puzzle
You want to fill a matrix of n rows and m columns with non-negative integers so that the sum
of each row or each column corresponds to a predetermined number. Each matrix entry also has
an upper bound constraint. Specifically, given non-negative integers r1,...,rn, c1,...,cm, and
b1,1,...,bn,m, find integers a1,1,...,an,m such that:
1. 0  ai,j  bi,j for all 1  i  n, 1  j  m;
2. ri = Pm
k=1 ai,k for all 1  i  n;
3. cj = Pn
k=1 ak,j for all 1  j  m.
(a) [10 Points] Design an algorithm to find such integers. Your algorithm should return NIL if
such integers do not exist.
3
(b) [8 Points] Prove the correctness of your algorithm.
(c) [2 Points] Analyze the running time of your algorithm.
BONUS QUESTION
Q5 [10 Points] Knight Coexistence
You want to place knights on an n ⇥ n chessboard. The chessboard has n2 positions from (0, 0)
to (n  1, n  1). A knight at position (x, y) is able to attack up to eight di↵erent positions:
(x + 2, y + 1), (x + 2, y  1), (x + 1, y + 2), (x + 1, y  2), (x  1, y + 2), (x  1, y  2), (x  2, y + 1),
and (x2, y 1) – for each position that lies on the board, of course. Moreover, some positions are
blocked so that you cannot place knights on them. Given n and a list of all blocked positions, find
a way to place as many knights as possible on the chessboard so that the placed knights cannot
attack each other.
4