Assignment 6
posted: 02.07.2021 due: midnight 16.07.2021
You can work in groups of up to three people. One group member should submit a copy of the solu-
tions on Brightspace, with all members’ names and banner numbers on it; the other group members
should submit text files with all members’ names and banner numbers (otherwise Brightspace won’t
let us assign them marks!). You may consult with other people but each group should understand
the solutions: after discussions with people outside the groups, discard any notes and do something
unrelated for an hour before writing up your solutions; it’s a problem if no one in a group can ex-
plain one of their answers. For programming questions you should submit your code, which should
compile and run correctly to receive full marks.
1. Show that Subset Sum is self-reducible: that is, if you have an algorithm that, given a set
S of integers and a target t, in polynomial time (in the cardinality of S) determines whether
a subset of S sums to t, then you can use it to design an algorithm that, given S and t, in
polynomial time (in the cardinality of S) returns such a subset.
2. A grid graph is a graph whose vertices are labelled with distinct pairs of integers such that a
vertex u labelled (x, y) is adjacent to a vertex v if and only if v is labelled (x−1, y), (x+1, y),
(x, y − 1) or (x, y + 1). HamPath is known to be NP-complete even when restricted to grid
graphs.
For the problem Wordz 2, we are given an n× n grid of characters, a dictionary of strings
and an integer k and asked if the grid contains at least k sequences of characters such that
� if a character in a sequence has coordinates (x, y), then the next character must have
coordinates (x− 1, y), (x + 1, y), (x, y − 1) or (x, y + 1),
� each character in the grid appears at most once across all of the sequences,
� each sequence is a distinct string in the dictionary.
The image below shows an instance of Wordz 2 with a 5×5 grid and the dictionary of English
words, with 4 sequences indicated with blue, red, green and purple. (The grey characters are
not a sequence, although they could be.)
Give a polynomial-time reduction from HamPath on Grid Graphs to Wordz 2. (You can
assume all the coordinates in the vertices’ labels in the graph are polynomial in the number
of vertices.)
Continued on next page!
1
3. For the problem Integer Linear Programming (ILP) we are given a set of linear con-
straints such as
3×1 + 5×2 ≤ 5
4×2 − 2×3 = 10
6×1 − x2 + 3×3 ≥ 6
and asked if there is a solution with all of the variables’ values integers. Give a polynomial-
time reduction from 3-Sat to ILP.
4. We can reduce 3-Col to Planar 3-Col in polynomial time. Why doesn’t our 3O(n
1/2 logn)-
time divide-and-conquer algorithm for Planar 3-Col give us a 3O(n
1/2 logn)-time algorithm
for 3-Col?
5. We saw a 2-approximation algorithm for the search version of Vertex Cover, and the
complement of a vertex cover is an independent set; does that mean we have a 2-approximation
algorithm for the search version of Independent Set? Why or why not?
2
“Clink” versus “BOOM”
I Divide and Conquer
Colouring Graphs
Assignment 1
Solution
Euclid, Karatsuba, Strassen
Fast Fourier Transform
Assignment 2
Solutions
Asymptotic Bounds
Sorting
Assignment 3
Solutions
II Greedy Algorithms
Huffman Coding
Minimum Spanning Trees
More Greedy Algorithms
Assignment 4
Solutions
Midterm 1
Solutions
III Dynamic Programming
Edit Distance
Subset Sum and Knapsack
Optimal Binary Search Trees and Longest Increasing Subsequences
Assignment 5
Solutions
IV NP-Completeness
Reductions
Cook’s Theorem
Assignment 6
Midterm 2
Solutions
V More Graph Algorithms
Assignment 7