The notation "CLRS Chap. 4.1" refers to Chapter 4.1 of the Cormen et al. text.
The notation "LN 4.1.15" refers to the instructor's Discrete Mathematics Lecture Notes, Chapter 4, problem 4.1.15.
The notation "ASY 2.21" refers to problem 2.21 in the Asymptotic Equality and Inequality handout.
"DO" problems are strongly recommended to check your understanding of the concepts; do not hand them in.
Problems labeled "HW" must be handed in at the beginning of the next class unless expressly stated otherwise.
BONUS PROBLEMS are not mandatory but the same deadline applies as to ordinary homework.
CHALLENGE PROBLEMS have no point value (but they earn you the
instructor's attention) and no deadline (except they expire when
discussed in class). Make sure you hand them in on a separate sheet,
state your name, the fact that this is a challenge problem
solution, and indicate the problem being solved. One further
request: if you hand in a solution a challenge problem, send email to the
instructor giving the problem number and the brief indication of the
problem. Such email will create an easy record and help avoid mistakes
in my records.
REWARD PROBLEMS are challenge problems that you should NOT hand in.
The solution is its own reward. No deadline. Of course you may discuss
your thoughts with the TA and the instructor.
If you hand in material before its due date, make sure you
put it on a separate sheet since solutions are graded in batches
by their due dates.
5.0 DO: Solve the test problems (third quiz, posted), including the
bonus problems.
5.1 DO: State the decision version of the "maximum independent set"
problem in an undirected graph. Prove that this problem is
NP-complete, via reduction from a probem shown NP-complete in class.
(This is a very easy problem, the reduction is described by a single word.)
5.2 DO: (a) The 3-CLIQUE problem asks whether or not a given undirected graph
has a triangle. Decide this question in O(n2.81) where
n is the number of vertices. (b) Decide the analogously defined
k-CLIQUE problem in O(n0.94k). Use only
results discussed in class.
5.3 DO: Find a deterministic polynomial-time algorithm which, given
a 3-CNF formula, finds an assignment that satisfies at least 7/8
of the clauses. (The solution is fairly simple but requires
a good idea.)
5.4 DO: The MAX-ACYCLIC-SUBGRAPH problem takes a directed graph
G = (V,E) as input and asks to find a largest acyclic subset
F ⊆ E (i.e., (V,F) must be a DAG (directed acyclic
graph)). This problem is NP-hard. Find a 1/2-approximation,
i.e., an acyclic subset F' ⊆ E that is at least half
as large as the largest acyclic subset. Find F' in polynomial time.
(The solution is very simple, just one line.)
5.5 DO: Prove that the SUBSET-SUM problem is NP-complete, via reduction
from the 3D-MATCHING problem (both problems were defined in class).
5.6 DO: Prove that the decision version of the Knapsack problem
with integer parameters is NP-complete, via reduction from
SUBSET-SUM. (Very simple, one or two lines.)
5.7 DO: Find a polynomial-time approximation scheme for the Knapsack
problem, i.e., for every ε > 0, find a polynomial-time
algorithm that produces a feasible solution (set of knapsack items satisfying
the weight constraint) of total value at least (1 - ε)-times
the optimum. (Hint: rounding and dynamic programming.)
4.1 DO: (a) Prove that addition of two n-digit integers can be
performed by a Boolean circuit of depth 4 and polynomial size.
Estimate the size of your circuit. (b) Improve depth 4 to depth 3.
4.2 DO: A celebrated theorem of Ajtai (1980) and Furst-Saxe-Sipser
(1981) says that PARITY (mod 2 sum) of n Boolean variables
cannot be computed by Boolean circuits of constant depth and polynomial
size. Use this result to prove that multiplication of
n-digit integers cannot be computed by Boolean circuits of
constant depth (say depth 10) and polynomial size.
4.3 DO: Let A be an n × n integral matrix (all entries are
integers). The bit-length
of such a matrix is the total bit-length
of the entires plus Θ(n2) for the symbols separating
the matrix entries. Let N denote the bit-length of A.
Prove: the bit-length of the determinant of A is O(N).
4.4 HW (feasible systems of linear equations):
A system of linear equations Ax=b (where A is a matrix, x is an
unknown column vector, and b is a given column vector) is feasible
if it has a solution. Let LIN denote the set of feasible systems
of linear equations with integer coefficients.
Prove: LIN ∈ NP. What is the witness? What do you need
to show about the witness? You may use Problem 4.3.
Do NOT use Problem 4.5. (8 points)
4.5 REWARD PROBLEM. Prove: LIN ∈ P (Jack Edmonds, around 1967).
DO: Why is this not obvious using Gaussian elimination?
Note: This result played a key role in developing the
notion of "polynomial-time computation."
4.6 DEFINITION: A linear program is a system of linear inequalities
written as Ax ≤ b where A, x, and b are as in Problem 4.4
and inequality between vectors is meant coordinatewise:
(a1, ... ,an) ≤ (b1, ... ,bn)
means (∀ j)(aj ≤ bj).
A linear program is feasible if it has a solution (in real numbers).
Let LP denote the set of feasible linear programs with integer
coefficients.
4.7 REWARD PROBLEM. Prove: LP ∈ NP. Do not use the
known fact that LP ∈ P (Khachiyan, 1979). DO: What is the
witness? Can you show that your witness is short?
What does "short" mean?
4.8 DEFINITION: Let ILP denote the set of those linear programs with integer
coefficients which have a solution in integers ("integer linear
programs").
4.9 REWARD PROBLEM. ILP ∈ NP. (Difficult!)
DO: Why is this problem difficult? What is a witness?
What do we need to show about the witness?
4.10 REWARD PROBLEM. (You may skip this problem.)
Find the "Farkas Lemma" on the web. Use the Lemma
to show that LP ∈ coNP. (Do not use that LP ∈ P.)
4.11 HW: (a)
Let (0,1)-LP denote the set those linear programs with integer
coefficients which have a solution in zeros and ones (every variable
takes a value in {0,1}). Prove: (0,1)-LP ∈ NP.
(b) Assuming that 3SAT ∈ NPC, prove that (0,1)-LP ∈ NPC.
(Give a Karp reduction. NPC denotes the class of NP-complete
languages.) (4+12 points)
4.12 DO: Prove: P ⊆ NP. What is the witness?
4.13 DO: (a) Observe that COMPOSITES (the set of composite numbers,
i.e., integers > 1 that are not prime) belongs to NP. (What
is the witness?) (b) Observe that PRIMES belongs to NP because
of the Agrawal-Kayal-Saxena (AKS) Theorem (2002) that PRIMES ∈ P.
(c) CHALLENGE PROBLEM. Prove that PRIMES ∈ NP without AKS
(V. Pratt, cca. 1978). State the length of your witness (or primality).
Hint: Prove and use the following Lemma:
A positive integer p is a prime if and only if there exists
a positive integer g such that
(i) gp-1 ≡ 1 (mod p); and
(ii) if 1 ≤ j ≤ p-2 then
gj ≢ 1 (mod p). (Use without
proof the theorem that if p is a prime number then a
primitive root mod p exists.)
4.14 DO: Recall the language FACT = {(x,y) | x,y ∈ N,
(∃ d)(2 &le d &le y and d | x ) }.
Prove that this language is Cook-equivalent to the computational
task of "factoring", i.e., given a positive integer, listing its
prime factors. When reducing "factoring" to FACT, state
the complexity of your algorithm (the exponent in O(nC))
and separately state the order of magnitude of the number of oracle
calls to FACT. (Order of magnitude: within a constant factor.)
(N denotes the set of nonnegative integers.)
4.15 DO: Prove: if NP ⊆ coNP then NP = coNP. (Note: it is
conjectured that NP ≠ coNP.)
4.16 DO: Prove that Karp-reducibility is a transitive relation among
languages. Given the exponents C1 and
C2 of the Karp-reductions
L1 <K L2
and L2 <K L3,
determine the exponent
of your Karp-reduction
L1 <K L3.
(The exponent of a reduction is C if the reduction
algorithm runs in O(nC) where
n is the length of the input.)
4.17 DO: Prove: if P ∩ NPC ≠ ∅ then P = NP. In other words,
if any one of the NP-complete problems can be solved in polynomial time
then all problems in NP can be solved in polynomial time.
(Note: it is conjectured that P ≠ NP. This conjecture is one of the seven
million-dollar "Millennium Prize Problems" named by the Clay Mathematics
Institute for mathematicians of the 21st century.) For instance, if
3-colorability of graphs can be decided in polynomial time, then
the factorization problem can be solved in polynomial time and thereby
RSA broken.
4.18 DO: Prove: if coNP ∩ NPC ≠ ∅ then NP = coNP.
In other words,
if any one of the NP-complete problems is well characterized then
all problems in NP are well characterized.
(Note: it is conjectured that NP ≠ coNP.
Question: if you settle the NP ≠ coNP question, will you get the
million dollar prize?)
4.19 HW. Prove that the language FACT is NOT NP-complete unless
NP = coNP. You may use without proof any of the other problems stated
in this homework set. (8 points)
4.20 DO: Let 3-COL denote the set of 3-colorable graphs. Define 4-COL
analogously. Give a simple Karp-reduction from 3-COL to 4-COL.
4.21 DO: Recall the defnition of NP from class. Omit the condition
|w| < |x|C. What class of languages does the modified
definition define? Prove your answer.
4.22 DO: Prove: NP ⊆ R
where R denotes the class
of recursive (a.k.a. computable) languages.
4.23 DEFINITION: Recall the definition of the class
RE
of recursively (a.k.a. computably) enumerable languages:
a language L is recursively enumerable
(belongs to
RE )
if it is the domain of a partial recursive function (computable
partial function), i.e., if there exists a Turing machine
(or a C program) which takes strings as inputs and halts
exactly if the input string belongs to L.
4.24 DO: Prove that a language L is recursively enumerable
if and only if either L is empty or it is the range
of some recursive (total) function.
4.25 DO: Prove that HALTING is
RE-complete in the sense that
every language in RE
is Karp-reducible to HALTING. (Here
RE
denotes the class of recursively (a.k.a. computably) enumerable languages.)
4.26 DO: Give a Karp-reduction from 3-COL to HALTING.
4.27 DO: (a) Prove that there is no Karp-reduction from HALTING to 3-COL.
(b) Prove that there is no Cook-reduction from HALTING to 3-COL.
4.28 DO: Prove:
RE ∩
coRE =
R.
3.1 DO (by Wed, Feb 10, before the tutorial) Solve the problems of
Quiz 2 (press "Tests" on the banner)
3.2 DO (by Wed, Feb 10, before the tutorial) Study the handout
"Loop invariants" (press "Handouts" on the banner).
Solve all the Exercises in that handout.
3.3 HW (emergency exits, due Thu, Feb 11): We are given
a weighted directed graph G=(V,E,w)
with nonnegative weights and a subset S of the vertices
(the "emergency exits"). From each
vertex, find a min-cost path to the "nearest emergency exit"
("nearest" in terms of total weight of the path).
These paths should form a forest (one tree for each
vertex in S). Prove that one can find this forest
in time O(n log n + m).
(Represent the forest by parent links.)
(10 points) Hint. Your solution should be very simple,
just a few lines. Note that if |S|=1 then the problem is exactly
the one solved by Dijkstra's algorithm.
3.4 HW (due Thu, Feb 11):
The greedy
matching problem.
Do not hand in solutions to the "verify" or "why" questions in the
preamble of the problem sheet; just solve them for your benefit.
Hand in solutions to the highlighted Problem ((a1) 4 points,
(a2) 8 points, (b) 5 points)
3.5 HW (due Tue, Feb 16)
Lovász toggle,
part (a)
(10 points)
Homework set #5 (posted Tue, Mar 9, noon; due Wed, Mar 10, before
the tutorial)
Homework set #4 (posted Fri, Mar 5, 5am; due Tue, Mar 9.
READ all problems, including the Challenge and Reward problems;
understand their difficulty. Much of the material serves as
a review of recent class material; about half the problems have
been assigned in class.)
Homework set #3 (posted Mon, Feb 8, 7am; due Wed, Feb 10 and later
as specified)
3.6 (Car race problem) (due Tue, February 16): DO (a); HW (b) (10 points); BONUS (c) (8 points) A request: If you hand in the solution before its due date, make sure you put it on a separate sheet with your name on it. Solutions are graded in batches by their due dates.
3.7 CHALLENGE PROBLEM (minimum max-cost spanning tree): The "max-cost" of a spanning tree in a weighted connected undirected graph is the weight of its heaviest edge. Find a minimum max-cost spanning tree (a spanning tree of smallest possible max-cost) in linear time. Use only tools we discussed in class.
2.1 Unless you have done so already, please answer the questionnaire on the course home page (by email! do not hand in), even if you are only auditing this course.
2.2 REVIEW: LN Chapters 6 and 7 (Graphs and Digraphs, Finite Probability Spaces)
2.3 In the handouts, most algorithms are described in "pseudocode." STUDY from these samples how to write pseudocode. Pseudocodes give exact loop structure (for, while) but may use English statements as instructions. The goal is clear logic, conciseness, elegance.
2.4 STUDY the following handouts (click the "Handouts" tab on the banner):
2.5 DO: solve the problems in ASY, Section 2
2.6 DO: (Find min) (Due Wed, Jan 27, before tutorial) Given n real numbers, we want to determine their min in the comparison model. (Comparisons cost one unit each, bookkeeping is free.) Prove: (a) n - 1 comparisons suffice. (b) n - 2 comparisons do not suffice.
2.7 DO: (Find min and max) (Due Wed, Jan 27, before tutorial) Given n real numbers, we want to determine both their min and their max in the comparison model. Prove: 3n/2 comparisons suffice. (Note that this is rather surprising; how can determining the min reduce the cost of determining the max?)
2.8 HW (k-way merge): Given k sorted lists of data (real numbers), merge them into a single sorted list using comparisons. Your algorithm should cost O(n log k) (including bookkeeping), where n refers to the total number of items on the k lists combined, and there is unit cost associated with each elementary operation with real numbers (comparison, copying, deleting) and each link update. Describe your algorithm in clean pseudocode. In the description you may refer to high level data structure commands implemented in class. Indicate why the algorithm will have the complexity (cost) stated. (12 points) Comment. Copying real numbers can be replaced by link updates, so the only operation with real numbers that we need is comparison.
2.9 HW: Interval Sum (Warning. This is a dynamic programming problem. Half the credit goes for the "brain" of your solution: a clear explicit (non-algorithmic) definition of the array of problems considered.) Elegance counts. (12 points)
2.10 HW (Integer Valued Knapsack (assigned in class)) Consider the knapsack problem with integer values (rather than integer weights, as in class - now the weights and the weight limit are reals). Let V denote the sum of all values. Solve the knapsack problem at cost O(nV). (Same warning as for the preceding problem.) (14 points)
2.11 HW (Coins in a line, due Thu, Jan 28): n coins of various values are arranged in a line. Alice and Bob take turns to remove a coin from an end of the line until all coins have been removed. Each player in their turn removes exactly one coin and the coin must come either from the right end or the left end of the line so the remaining coins remain contiguous. Each player wants to maximize the total value of the coins collected. Alice moves first. Find her optimal first move in O(n2) steps. (Each player plays optimally.) Hint: dynamic programming. (12 points)
Note that the natural greedy algorithm is not optimal. Example: if the coin values are 10, 25, 10, 1 cents then Alice should pick the penny because picking (greedily) the dime would permit Bob to pick the quarter.
2.12 REWARD PROBLEM (coins in a line, from Peter Winkler's "Mathematical Puzzles: A Conoisseur's Collection"): Prove: (a) if n is even, Alice can always collect at least half the value. (b) This is not the case for odd n. Give a counterexample for every odd n > 1. (c) Suppose there are only two kinds of coins, of value 100 and 101 cents. Prove that a random sequence of such coins is almost surely a counterexample when n is odd.
2.13 DO: write simple, elegant pseudocode for the HEAPIFY(L) operation which turns a list L into a heap in O(n). Use the array implementation of the complete binary tree to represent the topology of the heap. (Due Wed, Jan 27, before the tutorial)
2.14 HW (due Thu, Jan 28) "All-ones square." (12 points) Warning: this is a dynamic programming problem. Half the credit goes for the "brain" of the algorithm: a simple and accurate definition of the meaning of the entries of the array you will fill incrementally.
2.15 REWARD PROBLEM (convex hull): Given n points in the plane, find their convex hull in O(n log n) steps (comparisons and arithmetic operations with real numbers).
1.1 Please answer the questionnaire on the course home page (by email! do not hand in)
1.2 REVIEW: LN Chap 2 (asymptotic notation)
1.3 In the handouts, most algorithms are described in "pseudocode." STUDY from these samples how to write pseudocode. Pseudocodes give exact loop structure (for, while) but may use English statements as instructions. The goal is clear logic, conciseness, elegance.
1.4 STUDY the following handouts (click the "Handouts" tab on the banner):
1.5 DO: solve the problems in ASY, Section 2
1.6 HW: ASY 2.19 (8+8 points)
1.7 HW (due Tue, Jan 19): ASY 2.20 (16 points)
1.8 HW: ASY 2.21 (b) (3+8 points) (Part (a) is review from class; you are asked to reproduce it.)
1.9 (12 coins) (a) DO: Given 12 coins, one of which is fake, we want to find the fake coin and also decide whether it is heavier or lighter. Show that this can be done with 3 measurements on a balance. (A balance has two trays. You can put any number of coins on each tray. The outcome of a measurement is "Left heavy," "Right heavy" or "Equal.") (b) REWARD PROBLEM: Find an oblivious algorithm for this problem, i.e., specify your measurements (subsets of coins to put in each tray) in advance (you choice of which coins must not depend on the outcomes of previous measurements). Show that 3 measurements still suffice.
1.10 HW: (13/14 coins) Given n coins, one of which is fake, we want to find the fake coin and also decide whether it is heavier or lighter, using measurements on a balance. (a) Prove that 3 measurements are not enough if n = 14. (b) Prove that 3 measurements are not enough if n = 13. (3+7 points) (A correct solution to part (b) earns you all the 10 points.)
1.11 DO: (Find min) (Due Wed, Jan 13, before the tutorial)) Given n real numbers, we want to determine their min in the comparison model. (Comparisons cost one unit each, bookkeeping is free.) Prove: (a) n - 1 comparisons suffice. (b) n - 2 comparisons do not suffice.
1.12 DO: (Find min and max) (Due Wed, Jan 13, before the tutorial)) Given n real numbers, we want to determine both their min and their max in the comparison model. Prove: 3n/2 comparisons suffice. (Note that this is rather surprising; how can determining the min reduce the cost of determining the max?)
1.13 HW (communication complexity) Recall the attack of the little green men from the first class. (a) Write up the Rabin - Simon - Yao protocol form class (witout its error analysis) and state what it accomplishes. Ignore the specific numbers from the first class; your inputs X and Y should be n-bit strings over {0,1}. (b) Suppose Alice and Bob execute the Rabin - Simon - Yao protocol on the n-bit input strings X and Y and in the end Bob declares "x ≠ y." In this case we additionally require that Bob also find an address i where x and y differ: x[i] ≠ y[i]. (x, y are arrays: x[1..n], y[1..n].) Prove that this can be accomplished by an additional O((log n)2) bits of deterministic communication (back and forth) between Alice and Bob. (No more coins flipped.) (2+12 points)
1.14 DO (Strassen's matrix multiplication): If we multiply two n by n matrices according to the textbook definition, we need to perform O(n3) arithmetic operations. V. Strassen found that this was not optimal: he reduced the multiplication of two n by n matrices to multiplication of 7 pairs of (n/2) by (n/2) matrices. The cost of the reduction is O(n2) (it involves computing certain linear combinations of matrices of these dimensions and bookkeeping). (a) State the recurrence for the complexity T(n) of this algorithm. (b) Prove that T(n) = O(nα) where α = log27 ≈ 2.807355. (Assume n is a power of 2.)
1.15 REWARD PROBLEM (coins in a line, from Peter Winkler's "Mathematical Puzzles: A Conoisseur's Collection"): Prove: (a) if n is even, Alice can always collect at least half the value. (b) This is not the case for odd n. Give a counterexample for every odd n > 1. (c) Suppose there are only two kinds of coins, of value 100 and 101 cents. Prove that a random sequence of such coins is almost surely a counterexample when n is odd.
1.16 HW (due Tue Jan 19) (Evenly splitting the coins): Suppose we have 2n coins, some of which are fake. All the fake coins have equal weight, and they are lighter than the true coins (which also have equal weight). Using O(log n) measurements on a balance, divide the coins into two sets of n coins of nearly equal weight. "Nearly equal" means if the number of fake coins is even, they must be evenly split between the two parts; if their number is odd, one part must have exactly one more fake coin than the other part. Write your algorithm in elegant pseudocode. (12 points)