Homework set #7 (posted Tue, March 10, 1:30 pm. Due Thu, Mar 12, before class, unless expressly stated otherwise).

7.1 Study all chapters of KT relevant to the material discussed in class. (Due by the final exam.) Recent chapters include NP-compleness, hashing, and local search.

7.2 HW (potential function/local search): We are given a symmetric weight function w : [n] × [n] → R on the pairs (i,j) ∈ [n] × [n], i.e., w(i,j) = w(j,i), and we stipulate w(i,i)=0. We are also given a real number α, 0 < α < 1. A configuration is a coloring of the set [n] red/blue, which we represent as a function x : [n] → {1, -1}; R = {i : x(i)=1} and B = {i : x(i)=-1}. We define the weighted degree d(i) as d(i) = ∑_j w(i,j). We define the weighted cross-color degree d⁺(i) as d⁺(i) = ∑'_j w(i,j) where the summation is restricted to those j with x(i)x(j)=-1 (j's color differs from i's color). We say that a red node i is stable if d⁺(i) ≥ α d(i). We say that a blue node i is stable if d⁺(i) ≥ (1 - α) d(i). A configuration is stable if all nodes are stable. Prove that a stable configuration always exists. Use the potential function method: define a potential function P(x) (where x = (x₁,...,x_n)) such that the value P(x) decreases each time we switch the color of an unstable node. (10 points)

Homework set #6 (posted Thu, Feb 26 noon. Due Tue, Mar 3, before class, unless expressly stated otherwise).

6.1 DO: prove that the "FACT" language is Cook-equivalent to the Factoring problem (factoring integers into prime factors)

6.2 DO: 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 ∈ P.

6.3 DO: Prove: LP ∈ NP. Here LP denotes the set of feasible linear programs with integer coefficients. Do not use the known fact that LP ∈ P.

6.4 REWARD PROBLEM. Find the "Farkas Lemma" on the web. Use the Lemma to show that LP ∈ coNP.

6.5 HW Assume 3-SAT ∈ NPC. Prove: (0,1)-LP ∈ NPC. ((0,1)-LP consists of those linear progras with integer coefficients which admit a (0,1)-solution, i.e., a solution where every variable is 0 or 1.) (8 points)

6.6 DO: Prove: a language L is computably enumerable if and only if L is either empty or it is the range of a computable (total) function.

6.7 DO: Prove: R = RE ∩ coRE (where R denotes the set of computable languages and RE the set of computably enumerable languages)

6.8 DO: Prove that the intersection of two computably enumerable sets is computably enumerable.

6.9 DO: Prove: RE ≠ coRE

6.10 DO: Prove: if NPC ∩ P is not empty then P = NP.

6.11 DO: Prove: if NPC ∩ coNP is not empty then NP = coNP.

6.12 CHALLENGE PROBLEM. Prove, without using AKS, that FACT ∈ coNP.

6.13 DO: Prove: if FACT ∈ NPC then NP = coNP.

6.14 DO: Finish the proof of the Karp-reduction from 3-SAT to CLIQUE discussed in class: show how to infer a satisfying assigment from a clique of size m.

6.15 HW: 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. (10 points)

6.16 HW: 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. (8 points)

6.17 DO: Give a Karp-reduction from 3-COL to HALTING.

6.18 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.

Homework set #5 (posted Sun, Feb 8, 2 pm. Due Thu, Feb 12, before class, unless expressly stated otherwise. Slightly updated Feb 8, 6:45 pm; 5.3 and 5.9 are due Wed before tutorial.) Don't forget that problems 4.7(b), 4.8, and 4.9 are due Tue, Feb 10.

5.1 DO: Review KT, Chapters 4.4 (Dijkstra), 4.5 (min-cost spanning tree), 4.6 (Union-Find data structure), 5.4 (closest pair) (past due)

5.2 DO: (a) Describe the "pessimist's algorithm" for min-cost spanning tree in pseudocode. (b) Prove the algorithm is correct. (c) What data structure would we need for the analysis? (d) Prove the algorithm can be implemented in O(m²). (d) (CHALLENGE PROBLEM) Improve this bound.

5.3 DO (topological sort, due Wed, Feb 11, before tutorial): Recall from Discrete Math that a graph is acyclic if and only if it has a topological sort. Given a graph, find, in linear time, either a (directed) cycle or a topological sort. Write your algorithm is elegant pseudocode. (As usual, the graph is given by an array of adjacency lists.)

5.4 (Union rules): Recall that the hierarchical implementation of the UNION-FIND data structure requires a decision at each UNION request: "who is winning" (if i is the winner of UNION(i,j) then the arrow will point from the capital of country j to the capital of country i). Prove that under either of the following rules, the depth of all trees will remain < 1 + log n (base 2 logarithm): DO: (a) "bigger wins" HW: (b) "taller wins." (7 points) (The size of a country is the number of its cities. Its height is the length of the longest path from root to leaf. Ties are broken arbitrarily.)

5.5 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.

5.6 HW (emergency exits): 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.

5.7 HW (RANGE-SUM query): Organize the data (real numbers) in a dynamic data structure which will serve the following requests: INSERT(y) (inserts key y (a real number)) and RANGE-SUM(a,b) for any pair a ≤ b of reals, where RANGE-SUM(a,b) returns the sum of the data y in the range a ≤ y < b (a,b are real variables). Each request should take O(log n) time to complete, where n is the number of data currently stored. Describe how to maintain your data structure. -- This will be an augmented version of a tree data structure studied in class. Describe, exactly what additional information you need to store at each node; and show how to maintain that information after each INSERT. (8 points)

5.8 DO: A prefix code over the alphabet {0,1} is a set S of (0,1)-strings such that none of them is a prefix of another. (So for instance {01,001, 010} is a prefix code, but {01, 010} is not.) Prove: if S is a prefix code then
∑_{x ∈ S}2^-length(x) ≤ 1. (Hint: represent the prefix code as the leaves of a binary tree.)

5.9 DO (topology of AVL trees, due Wed, Feb 11, before tutorial): Prove that the minimum number of vertices in an AVL tree of height h is F_h+3-1 where F_n is the n-th Fibonacci number. (Assigned in class.)

Homework set #4 (posted Sat, Jan 31, 12:30 pm. Due Tue, Feb 3, before class, unless expressly stated otherwise.)

Last call: if you still have not answered the Questionnaire posted on the class home page, please do NOW.

4.1 DO: Study the "Amortized complexity" and "Loop invariants" handouts. (Click the "Handouts" tab on the banner.) Warning: the "Loop invariants" handout was revised on Jan 31, 2009; the "Amortized analysis" handout was updated on Feb 2, 2009, 7pm (3 typos were corrected; the student who noticed the typos received bonus points)

4.2 HW (Queue via stacks): Solve Example 2 from the "Amortized analysis" handout. Note that in part (a) you only need to prove correctness, not timing. Part (b) is about the complexity of the procedure. (7+9 points)

4.3 DO: Solve the problems stated in the "Loop invariants" handout.

4.4 HW (Dijkstra loop invariant): Exercise 2(b) from the "Loop invariants" handout. Assume 2(a) without proof. (8 points)

Note: an essential part of the proof was discussed in class. Your proof should cover all cases, including the one discussed in class. You may reproduce the proof from class or give an alternative proof that covers more cases at once. - In describing your proof, for a variable t, use the notation t_old and t_new to denote the value before entering and after completing the current round (current execution of the while loop (once)).

4.5 HW (Dijkstra loop non-invariant): Exercise 4(a) from the "Loop invariants" handout. (5 points)

4.6 HW (adjacency testing): Given a graph G = (V, E) with n vertices and m edges (as an adjacency list), set up a data structure which will permit answering adjacency queries (queries of the form "(i, j) ∈ E ?") in O(1). Your data structure should occupy no more than O(min{mn, n²}) space and it should take no more than O(min{mn, n²}) time to build. (8 points)

Two observations. (1) The adjacency list representation does not permit O(1)-time answers to adjacency queries. (Why?) (2) The adjacency matrix of a graph G = ([n], E) is the n × n array A with A[i,j] = 1 if (i,j) ∈ E and A[i,j] = 0 otherwise. The adjacency matrix representation does answer adjacency queries in O(1) time. However, if our graph is very sparse (much fewer edges than vertices), then the n² space taken up by the adjacency matrix is too much. You need to solve this very sparse case.

Homework set #3 (posted Sun, Jan 25, 11:45 pm. Due Tue, Jan 27, before class, unless expressly stated otherwise.) All problems that are due Jan 27 were stated in class. Don't forget that three problems from HW-2 are also due Jan 27. -- Problem 3.12 added Jan 12, noon, due Jan 29.

In this course, "graph" means directed graph. This deviates from our usage in Discrete Mathematics. The reverse of a graph is obtained by reversing every edge. A graph is undirected if it is identical with its reverse. Our two principal representations of graphs are the "edge-list" representation (this representation consists of the list of vertices and the list of edges) and the "adjacency array" representation, consisting of an array of adjacency lists (one list per vertex). Normally we do not permit these lists to have repeated items; one of the exercises below justifies this. The number of vertices is usually denoted by n; the number of edges by m. So each of these representations has length Θ(n+m) where the name of each vertex is viewed as taking up one unit of space. "Linear time" means the number of steps is linear in terms of the length of the input. So for graphs, this means O(n+m) (unless repeated items are expressly permitted).

3.1 DO: write pseudocode for counting sort.

3.2 DO: write pseudocode for radix sort where each input word has equal length. Do not copy words, only links.

3.3 DO: write pseudocode for radix sort where the input words have variable lengths. Do not copy words, only links. Make sure your algorithm runs in linear time (time O(n) where n is the total length of the input, i.e., the sum of the lengths of the input words). Copying a link counts as one step.

3.4 DO: Review the "Graphs and Digraphs" chapter from LN.

3.5 DO: (a) Given a graph in edge list representation, convert this to adjacency array representation in linear time. (b) Given a graph in adjacency array representation, convert this to edge list representation in linear time.

3.6 DO: Given a graph in adjacency array representation, convert this into a monotone increasing adjacency array representation (each adjacency list should be (strictly) increasing). (This, in particular, eliminates repetitions from each adjacency list.) Perform this in linear time.

3.7 DO: Given a graph in adjacency list representation, construct the adjacency list representation of the reverse graph in linear time.

3.8 DO: Given a graph in adjacency list representation, decide in linear time whether or not it is undirected.

3.9 HW (counting connected components): Given an undirected graph in adjacency list representation, count its connected components in linear time. Hint: you need to modify BFS. Copy the BFS pseudocode from class, insert all modifications, and indicate where a modification has occurred by a big *. Explain the meaning of each variable (in English). (8 points)

3.10 HW (due Thu, Jan 29)(strong connectivity): Decide in linear time wether or not a given graph is strongly connected. Your solution must be extremely short and elegant (no more than three essential lines) with reference to DO exercises above and to results proved in class. You may not refer to algorithms not covered either above or in class (such as DFS). (8 points)

Homework set #2 (posted Tue, Jan 20, 1:20 pm, due at various dates, starting Wed, Jan 21, before the tutorial)

2.1 DO: Asymptotically evaluate the total cost of MERGE-SORT (including bookkeeping). Start with the statement of the recurrent inequality satisfied by the cost function. (Stated in class; was due Jan 15)

2.2 DO: write simple, elegant pseudocode for the INSERT(key, H) and EXTRACT-MIN(H) operations, where H is a heap. Use the parent, left-child, right-child links (p(x), l(x), r(x) where x is the name of a node), do not use the array implementation of the complete binary tree. (Stated in class; was due Jan 20)

2.3 DO (A power series): Evaluate the power series f(x) = ∑ i xⁱ where the summation extends over the range i=0 to ∞. (|x| < 1). Your answer should be a very simple closed-form expression (no summation signs and dot-dot-dots). Hint. Take the derivative of the power series expansion of 1/(1-x).   Note that in class we found (by a different method) that f(1/2) = 2. Make sure your answer is consistent with this observation. The analysis of which algorithm required this summation? (Outlined in class. Due Wed, Jan 21, before the tutorial)

2.4 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 21, before the tutorial)

2.5 DO (Strassen's matrix multiplication): If we multiply two n by n matrices according to the textbook definition, we need to perform O(n³) 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(n²) (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 α = log₂7 ≈ 2.807355. (Assume n is a power of 2.) (Due Wed, Jan 21, before the tutorial)

2.6 HW (due Thu, Jan 22) (Sorting a heap): Suppose we have n data (real numbers) arranged in a heap; and the heap is implemented as an array (as in class). Prove that in order to sort the data, we still need to make asymptotically at least n log n comparisons. (Warning: this problem is NOT about the HEAPSORT algorithm. We are allowed to compare any pair of data and we have random access to any address. The problem says we don't start from scratch, the heap stucture means some comparisons have already been made, so if we take advantage of those comparisons, we may achieve some savings. You need to prove that the savings is asymptotically negligible. Note also that you need to prove more than an Ω(n log n) lower bound; you need to prove the number of comparisons required is greater than or asymptotically equal to n log n. (See Section 2 of the "Asymptotic Equality and Inequality" handout for this concept.) (8 points)

2.7 HW (due Tue Jan 27) (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)

2.8 HW (due Tue, Jan 27) (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. (8 points)   Comment. Copying real numbers can be replaced by link updates, so the only operation with real numbers that we need is comparison.

Homework set #1 (posted Sun, Jan 11, 11am, due Tue Jan 13 before class, except where specified otherwise)

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):

• Asymptotic Equality and Inequality (ASY) (an updated version of LN, Chap 2.2)
• Binary Search
• Dynamic Programming: The Knapsack Problem
• Divide and Conquer: the Karatsuba--Ofman integer multiplication algorithm
• The Method of Reverse Inequalities (due Thu Jan 15)

1.5 DO: solve the problems in ASY, Section 2

1.6 HW: ASY 2.21 (b) (8 points)

1.7 BONUS PROBLEM: ASY 2.20 (8 points, due Thu Jan 15)

1.8 (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.9 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)

1.10 DO: (Find min) (Due Thu, Jan 15) 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.11 DO: (Find min and max) (Due Thu, Jan 15) 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.12 HW: (Integer Valued Knapsack) 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). (Warning. Half the credit goes for the "brain" of your dynamic programming solution: a clear definition of the array of problems considered.) (16 points)