The notation "KT Chap. 4.1" refers to Chapter 4.1 of the Kleinberg - Tardos text.
The notation "LN 4.1.15" refers to the Instructor's 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 (copied from the problem announcement: like "n+1 numbers"
or "another limit related to the def of "e"" -- no detailed description
needed, this suffices to remind me which problem it was). Such
email will create an easy record and help avoid mistakes in bookkeeping.
-- Please also send me email at this time about challenge problems
to which you handed in solutions earlier in this course. This will
help me create a complete record.
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 TAs 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.
12.1 DO (bipartite matching):
Complete the "augmenting path algorithm" discussed in class, and its analysis,
to find a maximum matching in a bipartite graph. Specifically (a)
show how to find an augmenting path if there is one (by modified BFS); and
(b) prove that if there is no augmenting path then our current matching
is already maximum.
12.2 DO (polynomial identity testing): (a)
Let H be a set of N numbers and let
f(x1, ... , xn)
be a nonzero polynomial of degree d in n
variables. Select random numbers ai ∈ H
(i = 1,...,n). Prove:
P(f(a1, ... , an) = 0 ) ≤
d/N.
11.0 DO: (a) Study the proof of the NP-completeness of
3-COL (from KT). (b) Study the statement of the 3D-Matching problem
and spend 10 minutes studying the proof that it is NP-complete (KT).
11.1 DO (Two conjectures): Compare the following two conjectures:
(A) P ≠ NP ; (B) NP ≠ coNP. -- Which of the two is
stronger (implies the other)? In other words, if you prove (B),
does the Clay Institute owe you a million dollars?
Prove your answer.
11.2 DO (Factoring is not expected to be NP-complete):
(a) Prove: if a language belongs to coNP and is at
the same time NP-complete then NP = coNP.
(b) Prove: if the language FACT (the decision version of
factoring integers) is NP-complete then NP = coNP. (Hint.
Prove that FACT ∈ coNP. Use AKS.)
11.3 CHALLENGE PROBLEM (...not even under Cook reductions)
Prove: if 3-SAT is Cook-reducible to factoring integers then
NP = coNP.
11.4 DO (Knapsack is hard): (a) State the decision version of
the Knapsack problem. (b) Prove that it is NP-complete (assuming
integer weights and values). Use the NP-completeness of
SUBSET-SUM.
11.5 DO (Metric Travelling Salesman Problem (MTSP)): Input: a
metric on n points ("cities"), i.e., a "distance function"
d : [n] × [n] → R,
which is positive except d(i,i)=0; symmetric:
d(i,j)=d(j,i); and satisfies the
triangle inequality: d(i,j)+d(j,k) ≥
d(i,k). The salesman wishes to visit each city
exactly once and return to the city where he started. The cost
of the trip is the sum of the distances between consecutive stops.
He wants to minimize the cost. (a) State the
decision version of this problem. Prove that it is NP-complete,
via Karp-reduction from the language HAM (Hamiltonian graphs)
(assume HAM is NP-complete).
(b) (approximate optimum)
Find a route in polynomial time which is at most
twice as expensive as the optimal one. Hint. Use min
cost spanning trees. (c) (Reward problem) (better approximation)
Find a route in polynomial time which is at most
3/2-times as expensive as the optimal one. Use the fact that
a min-cost perfect matching can be found in polynomial time.
11.6 DO (Fibonacci enigma):
Prove that given n, the n-th
Fibonacci number cannot be computed in polynomial time.
11.7 DO (longest common substring): Given two strings
of over the English alphabet, find the length of their longest
common substring. A substring is obtained by deleting some
(perhaps none, perhaps all) of the letters.
The substrings need not be contiguous. Example: the longest
common substrings of DARWIN and CREATIONISM are AIN and RIN
(but AR and RA are not common substrings). Your algorithm
should run in O(mn) where m,n are the lengths
of the two strings.
10.1 HW (long witnesses):
Recall the formal definition of NP: a language
L ⊆ Σ* belongs to NP if and only if
(∃ L1 ∈ P)(∃ C)(∀
x ∈ Σ*)
(x ∈ L if and only if
(∃ w)(|w| ≤ |x|C and
(x,w) ∈ L1)). Professor Zahhak
assigns this definition as a quiz problem and catches
Armayel and Garmayel cheating because they make the identical
mistake of omitting the statement
|w| ≤ |x|C
from the definition. What class of languages did
Armayel and Garmayel define? (This class was
named in class.) Prove your answer. (8 points)
(For 1 bonus point: where are the snakes?)
10.2 HW (coloring vs halting):
(a) Give a Karp-reduction from 3-COL to HALTING.
(b) Prove that there is no Karp-reduction from HALTING to 3-COL.
(Recall that 3-COL is the set of 3-colorable graphs and HALTING is the
set of programs in C which take no input and terminate in a finite
number of steps.) (8+8 points)
(Comment added 3-2 10pm: Your solution need not contain
any C code; the description of any such program in pseudocode
suffices.)
10.3 HW (the more colors, the merrier) (due Thu, March 6):
Assuming that 3-COL is NP-complete, prove that
4-COL is NP-complete. Your solutions should be very short and
simple. (10 points)
10.4 DO (complexity sandwich):
Find three languages
L1 ⊂ L2 ⊂ L3
such that L1 and L3
are undecidable and L2 ∈ P.
10.5 DO (linear and integer programming feasibility)
(due, Wed March 5, before the
tutorial): A linear inequality is an inequality of the
form a1x1 + ... +
anxn ≤ b
(all ai and b are real).
A system of k linear inequalities in n variables
can be compactly described as Ax ≤ b where
A is a k × n matrix, x
is the transpose of the vector (x1, ... ,
xn), and b is the transpose of the vector
(b1, ... , bk). (An inequality
between vectors is defined by requiring the inequality to hold
for each coordinate:
(r1, ... , rk)
≤ (s1, ... , sk)
means ri ≤ si for all i.)
The linear programming feasibility problem is the question
whether or not a given system of linear inequalities has a
solution. Let S be a subset of the real numbers.
The system is feasible in S if it has
a solution consisting of n numbers xi ∈
S.
We say that a system of linear inequalities has integer coefficients
if all entries of A and b are integers.
Let the language LPF consist of those systems of linear inequalities
with integer coefficients which are feasible in rational numbers; let
ILPF consist of those instances of LPF which are feasible in integers;
and let (0,1)-ILPF
consist of those instances of LPF which are feasible in {0,1}.
By definition, (0,1)-ILPF ⊆ ILPF ⊆ LPF.
(a) Show that these inclusions are proper.
(b) Give an example of a system of linear inequalities where
all coefficients are 0, 1, or -1,
such that the system belongs to LPF but not to ILPF.
Make your matrix as small as possible.
(c) We want to prove that ILPF ∈ NP. Jack suggests to use
a solution as a witness of feasibility. Why is this answer problematic?
(d) Prove that LPF ∈ NP. Use the fact if a system
of linear inequalities is feasible (in reals) then it has a solution
with the following property: for some t, there are n - t
variables of value 0; and omitting their columns from A,
the remaining matrix has t linearly independent rows
such that in each if these rows, equality holds. In other words,
the t nonzero variables satisfy a system of t
equations defined by a nonsingular t × t submatrix of
A.
(This is equivalent to a theorem called "Complementary slackness.")
10.6 HW (0-1 linear programming) (due Thu, March 6, before
class): Assuming 3-COL is NP-complete, prove that (0,1)-ILPF
is NP-complete. (Your solution should be very simple.)
(10 points)
Note that 8.6 is due simultaneously with this set of problems.
9.1 HW (3-colorability vs 3-coloring):
Suppose we are given a black box that recognizes the
language 3-COL. (Recall that such a black box takes as input an
undirected graph and answers "yes" if the graph is 3-colorable, "no"
otherwise.) Given a 3-colorable graph, use the black box to find a
3-coloring in polynomial time. Describe your algorithm in pseudocode.
State the number of calls your algorithm makes to the black box.
(10 points)
9.2 DO (certifying primality): Understand what exactly needs
to be proved in the following CHALLENGE PROBLEM:
Prove: PRIMES ∈ NP. (Of course
you are not permitted to use the AKS Theorem that PRIMES ∈ P.
AKS = Agrawal, Kayal, Saxena.)
Hint. Primitive roots mod p.
This result was proved by Vaughan Pratt in 1975. The title of
Pratt's paper is helpful: "Every prime has a succinct certificate."
Here "succinct" means "of polynomial lengths" (in terms of the
bit-length of the input number); "certificate" is synonymous
with "witness" in our context.
9.3 DO (NP ⊆ EXPTIME): Prove: if L ∈ NP then
membership in L
can be decided in exponential time. (An exponential
upper bound means an upper bound of the form O(2nc)
for some constant c.)
8.0 DO: Solve the Midterm problems without the time pressure.
8.1 DO: Study the handout "Repeated squares and Euclid's Algorithm"
(Click "Handouts" on the banner)
8.2 DO (RSA vs factoring):
Let x and y be integers. Let
N = xy and M = (x - 1)( y -1).
Given N and M, determine x and y
in polynomial time. Find the smallest exponent.
8.3 BONUS PROBLEM: Given the positive integers k
and m, find (Fk mod m) in polynomial time.
- Your solution should be elegant, just a few lines.
(Fk is the k-th Fibonacci number.)
(8 points)
8.4 DO (medians of k-windows):
Let k be an odd positive integer, k ≤ n.
Given an array A[1..n] of real data,
let B[i] be the median of the subarray
A[i..i+k-1] (k numbers).
Compute the array B[1..n - k +1]
in time O(n log k). Hint. Use a
data structure studied in class.
8.5 DO (greedy graph coloring): Solve the following
problems in linear time. Write your solution in elegant
pseudocode. (a) Given an undirected graph with maximum degree d,
find a legal coloring with at most d + 1 colors.
(b) Given an undirected graph, either find (b1) a legal coloring
with at most 6 colors or (b2) find a proof that the graph is not planar.
In the latter case, return "NOT PLANAR" along with very simple evidence
of this conclusion. (Note that (b1) and (b2) are not mutually
exclusive but all graphs fall in at least one of these two
categories.)
8.6 HW (due Thu, Feb 28: critical path): Given a weighted DAG and
two vertices, s and t, find, in linear time, the most expensive
s → t path. Negative weights are permitted. Write your
elegant algorithm in pseudocode. Hint. Dynamic programming.
(8 points) (Comment added 3-11: Sorry, this hint was
somewhat misleading. The solution involves an "update" operation like those
used in BFS and Dijkstra.)
Homework set #12 (posted Thu March 6, 11:59 am; due Tue March 11 before class)
(b) (Schwartz - Zippel) Let
f(x1, ... , xn)
be a polynomial of degree ≤ d; possibly the zero polynomial.
Suppose we have a black
box that, given any numbers ai, outputs
f(a1, ... , an).
Give a randomized algorithm that will decide whether or not
f is identically zero in the following sense:
Let us choose any ε > 0 in advance. Then
(So if the algorithm outputs 0, we know that f is not
identically zero; if the algorithm outputs 1, we can bet
that f is identically zero; we can make the bet as safe as we wish).
The algorithm should make O(log(1/ε)) calls to the black box;
and each time, the numbers ai should be from
the set {1,2,...,2d}.
Homework set #11 (posted Tue March 4, 11:59 pm; due Tue March 11 before class)
Homework set #10 (posted Sat March 1, 10:40 pm; due Tue March 4 before class)
Homework set #9 (posted Tue Feb 26, 1:15 pm; due Thu Feb 28 before class)
Homework set #8 (8.1- 8.3 posted Wed Feb 20, 7pm; 8.4 - 8.6
posted Mon Feb 25 1:35pm. All except 8.6 due Tue Feb 26 before class)
Homework set #7 (posted Thu Feb 14, noon; due Tue Feb 19 before class)
Go to top
7.1 DO: Study KT, Chapters 13.6 (hashing)
7.2 DO: Review Number Theory from Discrete Math (gcd, congruences, multiplicative inverse, Fermat's Little Theorem, CRT)
7.3 DO (Euclid's algorithm): Prove that Euclid's algorithm runs in polynomial time. Give the smallest valid exponent, assuming multiplication of n-bit integers takes O(n2) (no fancy multiplication) and the same complexity applies to long division (division with remainder). Hint: if a and b are n-bit positive integers, prove that Euclid's algorithm to compute gcd(a,b) terminates in ≤ 2n rounds.
7.4 DO (small cliques): Decide whether or not a given graph has a clique (complete subgraph) of size 10 in polynomial time.
7.5 BONUS PROBLEM, due Thu Feb 21 (fast triangles): Decide whether or not a given undirected graph has a triangle (K3 subgraph) in time O(n2.81). (n is the number of vertices.) (8 points)
7.6 HW, due Thu Feb 21 (fast adjacency testing): Given a graph, design a data structure which permits adjacency queries in O(log n) time. You should construct your data structure in (deterministic) linear time and it should occupy linear amount of space. (So you cannot use the adjacency matrix (not linear space) and cannot use hashing (randomized).) Make your data structure (a) static (no edge insertions/deletions) and extremely simple; (b) dynamic, with O(log n) update time per insertion (adding a new edge, deleting an edge). (Here "linear time" refers to O(n+m) basic operations with the names of the vertices (comparison, copying, etc.). Do NOT worry about bit-complexity in this problem, the analysis should be made in the style of previous graph algorithms like BFS, Dijksta, Jarník). (6+4 points)
7.7 HW, due Thu Feb 21 (Moby-Dick): KT Problem 6/6
(pp. 317-318). Given the lengths of the n words comprising
the text and the length bound L, solve the problem in
O(n3) steps, where one step is an arithmetic,
comparison, or bookkeeping operation involving numbers not greater
than the square of the
sum of all the input numbers. Describe yor solution
in elegant pseudocode. The clear definition of the array of
problems (brain) accounts for 4 out of the 12 points.
Hint.
From the required time bound, do NOT draw the conclusion that
you need to deal with a 3-dimensional array of subproblems.
(Correction: "the square of" added 2-18-08, 1:30am.)
Correction: "O(n3)" should be
"O(n2)."(Added 2-20-08. Due to the late
announcement, O(n3) solutions will also be accepted.)
REMEMBER: if you submit a solution before its deadline, make sure you write it on a separete sheet. Grading is done in batches according to due dates.
6.1 DO: Study KT, Chapters 4.6 (Kruskal, Union-Find) and 5.4 (closest pair)
6.2 DO (topological sort): 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.)
6.3 (Union rules): The forest implementation of the UNION-FIND data structure required 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) "deeper wins." (10 points) (The size of a country is the number of its cities. Ties are broken arbitrarily.)
6.4 CHALLENGE PROBLEM (min 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.
6.5 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.
6.6 DO (Strassen's matrix multiplication): Strassen 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.
6.7 REWARD PROBLEM (convex hull): Given n points in the plane, find their convex hull in O(n log n).
6.8 HW (range 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(a,b) for any pair a ≤ b of reals, where RANGE(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. (8 points)
6.9 HW (polynomial growth): For each of the following sequences,
determine whether or not it is polynomially bounded. If it is, state
(precisely) the set of valid exponents.
(C is a valid exponent for the sequence
{an} if an=O(nC).)
(a) (ln n)ln ln n
(b) (ln ln n)ln n
(c) [ln n]! ([x] means the rounded-down value
of x ("floor")) (d) 5ln n.
(4+4+4+4 points)
6.10 BONUS PROBLEM (growth of a recurrence):
Let the function f(n) satisfy the recurrence
f(n) = f(n-1) +
Af([√n]) where A is a
positive constant.
(a) Prove that for every A >0, this sequence is polynomially bounded.
Determine the exact set of valid exponents if (b) A ≤ 2
(c) A > 2. (2+3+3 points)
Added on Feb 21. Two conditions should be added to the
satetement of the problem: (1) f(n) > 0 for all n;
(2) the recurrence is assumed to hold for n≥ 2.
Apparently none of the attempted solutions was influenced by these
omissions.
6.11 HW (knapsack): Consider the knapsack problem with integer weights and integer values. We solved this problme in O(nW) steps where W is the weight limit. Show that this solution is NOT polynomial time in the following sense. Let N denote the bit-length of the input (total number of binary digits needed to specify all weights and values). Then there do not exist constants A, C such that nW ≤ ANC for all sufficiently large inputs. (9 points)
5.1 DO: Study KT, Chapters 4.1-4.5 (greedy algorithms for scheduling and minimum cost spanning trees)
5.2 DO: Study MN (Discrete Math text), Chapters 4.3-4.5 (spanning trees)
5.3 DO: Study the handouts "Amortized analysis" and "Loop invariants" (click the "Handouts" tab on the banner)
5.4 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)
5.5 DO: Solve the problems stated in the "Loop invariants" handout.
5.6 HW (Dijkstra loop invariant): Exercise 2(b) from the "Loop invariants" handout. Assume 2(a) without proof. (6 points)
5.7 DO: Describe the "pessimist's algorithm" for min-cost spanning tree. (b) Prove the algorithm is correct.
5.8 HW: All-ones square. (10 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.
5.9 DO: Our solution to the Knapsack Problem with integer weights (handout) gave the maximum weight under the given constraint but did not reveal an optimal subset. Modify the algorithm so as to produce an optimal subset within the same time bound.
5.10 (Car race problem) (due Tue, February 12): DO (a); HW (b) (10 points); BONUS (c) (8 points)
5.11 CHALLENGE PROBLEM: We have n coins; some of them fake. All fake coins weigh the same and they are lighter than the fair coins. Count the fake coins using O(log2 n) measurements on a balance. OPEN PROBLEM: do o(log2 n) measurements suffice?
Remember: Problems 3.2, 3.3, 3.5 are due with today's problem set.
4.0 If you have not done so yet, answer the questionnaire on the course home page (by email! do not hand in)
4.1 DO: Solve Quiz-1, including the bonus problems. (Click the "tests" tab on the banner to find Quiz-1.)
4.2 HW: Give a linear time algorithm to decide whether or not a given graph is strongly connected. Describe your algorithm in pseudocode. Algorithms for which a pseudocode was presented in class can be used as subroutines (you don't need to copy the pseudocode). The same applies to algorithms previously assigned as (ordinary, not bonus of challenge etc) homework. As always in this class, "graph" means digraph and your input graph is given as an array of adjacency lists. Hint. Your solution should be very simple (essentially 3 lines). (8 points)
4.3 BONUS PROBLEM (coins in a line): 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. (8 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. Now out of 10, 25, 10, no matter what Bob picks, the quarter will go to Alice. So if each player plays optimally, Alice will collect 26 cents, while Bob gets 20.
4.4 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.
4.5 HW, due Thu, Jan 31 (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, n2}) space and it should take no more than O(min{mn, n2}) time to build. (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.
Two observations. (1) The adjacency list representation does not permit O(1)-time answers to adjacency queries. (Why?) (2) 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 n2 space taken up by the adjacency matrix is too much. You need to solve this very sparse case.
3.0 If you have not done so yet, answer the questionnaire on the course home page (by email! do not hand in)
3.1 STUDY the "Dynamic Programming: The Knapsack Problem" handout (click the "Handouts" tab on the banner)
3.2 HW (due Tue Jan 29): (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)
3.3 HW (due Tue Jan 29): Interval Sum (12 points)
3.4 HW: (Graph Reversal) Given a graph G in adjacency array (i.e., array of adjacency lists [added on Jan 23, 11pm]) representation, find an adjacency array representation of the reverse graph Gop (obtained by reversing every arrow). (Recall that in this class, "graph" means digraph.) Your algorithm should work in linear time. Write your solution in clean pseudocode. Explain your variables. Elegance counts. You may use an algorithm learned in class as a subroutine without giving its pseudocode. (Recall: "linear time" means O(n+m) where n is the number of vertices and m is the number of edges.) (8 points)
3.5 HW (due Tue Jan 29): (Recognizing Undirected Graphs) Given a graph G in adjacency array representation, decide in linear time whether or not G is undirected. Write your solution in clean pseudocode. Explain your variables. Elegance counts. (10 points)
3.6 DO: (Counting Sort) Write a pseudocode for the last phase of Counting Sort (where we turn the counting array into the output (sorted) array).
3.7 DO: (Radix Sort) Write a pseudocode for Radix Sort (a) assuming all items have the same length; (b) without this assumption. Your algorithm should run in O(N) time where N is the total number of characters in the input. (We assume the alphabet is of bounded size.)
2.1 REVIEW pseudocodes from class and the handouts
2.2 HW: write elegant pseudocodes for the "INCREASE-KEY(Q, address, newkey)" ("bubble down") and "INSERT(Q,key)" commands, where Q is a heap. (Do not analyze.) (4+4 points)
2.3 HW: (A power series) Evaluate the power series f(x) = ∑ i xi 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). (5 points) Note that in class we found (by a different method) that f(1/2) = 2. Make sure your answer is consistent with this piece of data. The analysis of which algorithm required this summation?
2.4 HW: (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.5 (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.
2.6 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+6 points)
2.7 DO: (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.
2.8 DO: (Find min) 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.9 DO: (Find min and max) 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.10 HW: 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, (a3) 5 points)
2.11 HW: (due Thu, Jan 24) (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. (6 points) Comment. Copying real numbers can be replaced by link updates, so the only operation with real numbers that we need is comparison. This problem was updated at 11:10pm on Thu, Jan 17.
1.1 REVIEW: LN Chap 2 (asymptotic notation)
1.2 STUDY: KT Chap 4.1 (Interval Scheduling)
1.3 STUDY the following handouts (click "Handouts" on the banner):
1.4 DO: solve the problems in ASY, Section 2
1.5 HW: ASY 2.21 (b) (8 points)
1.6 BONUS PROBLEM: ASY 2.20 (8 points, due Tue, Jan 22)