HW#1 --- last modified March 02 2019 21:30:58..
Solution set.
Due date: Sep 11
Files to be submitted:
Hw1.tex
Hw1.zip
Purpose: To refresh our knowledge of O, Ω, Θ notation. To explore
the relationship between decision problems and optimization problems. To begin studying
formal machine models.
Related Course Outcomes: We are learning about the machine models
needed for outcome (1) Exhibit a simulation of one machine model with another.
Specification:
This homework consists of two parts: a written answer part (the first three items below) and a
coding part (the last numbered item below). I expect you to work in groups of up to three people. Do not share code or solutions between
groups. The written part of the homework should be typeset in LaTeX and submitted as
Hw1.tex. Your coding project should be submitted in the ZIP file Hw1.zip.
1. Prove carefully that
(a) ∑ni=1(1/i) = O(log
n).
(b) n! = Ω(n10000).
(c) ∑ni=0(i*n3) =
Θ(n5).
2. Assume we are working over a unary alphabet I. Give the formal description of
a Turing Machine which decides if the input is a power of 3.
3. Analyze the proof of Theorem 2.1 in the book to determine the space complexity of
the algorithm given for simulating a k-tape Turing Machine by
a 1-tape Turing Machine. Justify your answer.
4. For the coding parting of the assignment, you will implement the algorithm for MATCHING
described in Chapter 1 of the book. After being compiled with the command
javac *.java, your program will be run from the command line with a command like:
java Matching adjacency_string0 adjacency_string1 adjacency_string2 ...
For example,
java Matching "1 2 3" "2 4" "3" "0" "0 1 2 3 4"
The command line arguments are supposed to represent a bipartite graph. Let
U={u0, u1, ..., un} and
V={v0, v1, ..., vn} be
the disjoints sets of this graph. Then adjacency_stringi lists
all the nodes in V connected to ui. So for example, the string "1 2 3"
in above says that u0 is connected by an edge to
v1, v2, v3. You can assume that the number of nodes
in U and V is the same as the number of strings listed as input. You do not need
to check for illegal inputs.
Based on these inputs, your program should construct the capacity matrix of the 2n+2
node network which results from using the reduction in the book from MATCHING to MAX FLOW(D).
For simplicity in this network we will label the nodes from U as 0 to n-1, the nodes from
V from n to 2n-1, the node s will be node 2n, and the node t will be node 2n+1. Your program
should then pretty print to the screen this matrix.
For the example command line above, one might get:
0 0 0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
Your program should then construct a max flow (use the breadth first variant
from the book) for the network you got and pretty print its capacities. Finally,
your program should write `yes' if the max flow has value n or larger
and print `no' otherwise. Here `yes' will mean the original bipartite graph
had a matching and `no' will mean it didn't.
Point Breakdown
LaTeX file compiles, Java Coding Guidelines followed for Program |
1pt
|
Problems 1-3 above (1pts each) |
3pts
|
Program correctly pretty prints the network capacity matrix on test cases |
2pts
|
Program correctly pretty prints the max flow capacity matrices on test cases |
2pts
|
Program outputs `yes' `no' correctly on test cases |
1pt
|
Manual code inspection of your max flow algorithm seems fine |
1pt
|
Total | 10pts |
|