"DM 4.1.15" refers to item 4.1.15 (Chapter 4, Section 1)
in the instructor's online
Discrete Mathematics Lecture Notes.
WARNING. Skip DM Section 2.2 and Chap. 7. DM Sec 2.2 is replaced
by ASY (below) and DM Chap. 7 is replaced by PROB (click "Texts"
on the banner).
"ASY 6.21" refers to item 6.21 (Section 6) in the Asymptotic Equality and Inequality handout.
"PROB 7.4.22" refers to item 7.4.22 (Section 4) in the handout Finite Probability Spaces.
"LinAlg 6.1.14" refers to item 6.1.14 (Chapter 6, Section 1) in the instructor's online text Discover Linear Algebra.
"COMP" refers to the Computability and Complexity handout.
Please check the explanation of the various categories of exercises (DO, HW, Bonus, Challenge, Reward problems).
If you suspect an error, please notify me (the instructor) by email. Inevitably, I make errors. Please read the instructions regarding instructor's errors. Apply your critical thinking to whatever I say or write. I will be grateful for corrections. You can warn me during class via zoom's private "chat" and outside class by email.
All exercises are due Fri, Mar 19 at 6pm.
26.05 MATERIAL COVERED.
Linear Programming decision problem in $\NP\cap\coNP$.
The ellipsoid method: Soviet mathematicians of the 1970s:
Naum Shor, A.S. Nemirovski--D.B. Yudin. 1979: Leonid Khachiyan:
LP in polynomial time. Ellipsoid, volume reduction. Minimum
volume of simplex defined by inequalities with integer coefficients.
Estimating the number of rounds in terms of the bitlength of
the input. Convex optimization with separation oracles.
Weighted matching problem: the Edmonds polytope.
26.15 STUDY the material recently (3-12) posted for Class 23 (below)
and solve the problems stated there.
26.25 DEF The integer LP problem (ILP) takes as input the
integer matrices $A,b,c$ and seeks to maximize the goal function
$c^Tx$, subject to the given constraints $Ax\le b$, where $x\in\zzz^n$
(maximum/supremum over all integer vectors).
26.30 CH (ILP feasibility) Prove: the ILP feasibility problem
(does there exist an integer vector that satisfies the constraints $Ax\le b$)
is in $\NP$. What is the witness, and what is the difficulty with
this witness?
26.35 DEF The (0,1) LP problem (01-LP) takes as input the
integer matrices $A,b,c$ and seeks to maximize the goal function
$c^Tx$, subject to the given constraints $Ax\le b$, where $x\in\{0,1\}^n$
(maximum/supremum over all $(0,1)$-vectors).
26.40 HW (18 points) Prove that the 01-LP feasibility problem
(does there exist a $(0,1)$-vector that satisfies the constraints)
is $\NP$-complete. Use Karp reduction from 3SAT. Do not use
the challenge problem above (26.30).
26.50 Bonus (20 points) The weighted minimum cover
problem takes as input a graph $G=(V,E)$ and a weight function
$f:V\to \nnn$ (positive integer weights) and seeks to minimize the
total weight of a cover. (a) State this as an ILP problem.
(b) Obtain a polynomial-time 2-approximation to the optimum
using linear programming and rounding. (So you need to find
a cover of which the weight is at most twice the optimum weight.)
Analyze the algorithm (prove the approximation factor,
reason the polynomial time). Make your solution short
and elegant.
26.60 HW (8 points) We perform DFS on a digraph $G$.
Let $u$ and $v$ be vertices. True or false: If $d_u < d_v$
($u$ is discovered before $v$) and $v$
is accessible from $u$ then $v$ is a descendant of $u$.
26.65 HW (10 points) Prove the nontrivial direction
of the White Path Theorem (again!) (16.72): If at time $d_u$
there is a white path from $u$ to $v$ then $v$ is a descendant
of $u$.
More to follow. Please check back later.
All exercises are due Fri, Mar 19 at 6pm.
25.05 MATERIAL COVERED.
Coping with $\NP$-completeness: approximation algorithms.
Fully polynomial-time approximation scheme for Knapsack:
approximating Knapsack within a $(1-\varepsilon)$ factor
in $O(n^3/\varepsilon)$ time in the unit cost model
(operations with real numbers at unit cost: arithmetic,
comparison, rounding). Branch-and-Bound:
Finding maximum independent set in a graph
in time $O(c^n)$ where $c\approx 1.38$ is the only root
$c > 1$ of the polynomial $x^4-x^3-1$.
25.10 DEF Recall that the input to the Knapsack problem
is a list of $2n+1$ positive reals, $v_1,\dots,v_n$ (the values),
$w_1,\dots,w_n$ (the weights), and $W$ (the weight limit).
We say that a subset $I\subseteq [n]$ is feasible if
$\sum_{i\in I} w_i \le W$ (the weight constraint is satisfied).
We wish to maximize the goal function $\sum_{i\in I} v_i$
for feasible sets $I$. The integer Knapsack problem is the same
problem restricted to integral inputs (all values and weights
are integers).
25.15 THEOREM The decision version of the integer Knapsack
problem is $\NP$-complete.
25.17 HW (4 points) Theorem 25.15 refers to the integer
Knapsack problem. Would the same $\NP$-completeness statement
be false if we omitted the word "integer"? Reason your answer.
25.20 DEF Let $f:\Sigma_1^* \times \Sigma_2^*\to \nnn$
and $g:\Sigma_1^*\to \nnn$ be functions. The (discrete)
maximization problem
for $f$ takes as input a string $x\in\Sigma_1^*$ and seeks to
maximize $f(x,y)$ over all strings $y\in\Sigma_2^{g(|x|)}$
(strings of length $g(|x|)$ over the alphabet $\Sigma_2$).
Discrete minimization problems are defined analogously.
The common name of the two types of problems is
(discrete) optimization problem.
25.22 DEF Let $\max(f,g,x)$ denote the maximum value for the
maximization problem above. For $\alpha < 1$, an
$\alpha$-approximation (or approximation within
a factor of $\alpha$) to this maximization problem is to find
a string $y\in\Sigma_2^{g(|x|)}$ such that
$f(x,y) \ge \alpha \max(f,g,x)$. In the
case of a minimization problem we take a value $\beta > 1$
and look for $y$ such that $f(x,y) \le \beta \min(f,g,x)$.
(The notation $\min(f,g,x)$ should be self-explanatory.)
25.24 DEF A polynomial-time approximation scheme (PTAS)
for the optimization problem defined by the pair $(f,g)$ of
functions is an algorithm that, for every $\eps > 0$,
finds a $(1-\eps)$-approximation in polynomial time
in case of a maximization problem. For minimization problems,
it finds a $(1+\eps)$-approximation.
The polynomial may depend on $\eps$.
25.27 HW (18 points) Prove that, given $\eps > 0$,
the Knapsack problem can be solved within a factor of $(1-\eps)$
in time $O(n^3/\eps)$ in the unit cost model, where the following
operations on real numbers can be performed at unit cost:
arithmetic, comparison, rounding. Follow the outline given
in class.
25.29 HW (9 points) Infer from the preceding exercise
that the integer Knapsack problem has a FPTAS. State the polynomial
time bound in terms of the bitlength $N$ of the input and the quantity
$1/\eps$. (Write $N$ to denote the bitlength of the input, and
keep $n$ to denote the number of items.)
25.40 HW (15 points) Let $c$ denote
the only root of the polynomial $x^4-x^3-1$ that satisfies $c > 1$.
(So $c\approx 1.38$.)
Let $T(n)$ denote a sequence of positive numbers satisfying the recurrent
inequality
$T(n) \le T(n-1)+T(n-4)+O(n^2)$ $(n\ge 5)$. Prove: $T(n) = O(c^n)$.
25.43 HW (7+13 points) Recall that $\alpha(G)$ denotes the size of
the largest independent set of the graph $G$, and a maximum independent
set is an independent set of size $\alpha(G)$.
Below we continue to use the notation of DEF 25.20.
25.50 DEF A local search algorithm for a maximization
problem picks a string $y_0$ and then searches for a string $y$
in the vicinity (by some metric) of $y_0$ such that
$f(x,y) > f(x,y_0)$. If such a string is found, replace $y_0$
by $y$ and repeat.
25.52 DEF Let $\Sigma_2=\{0,1\}$ (the string $y$ is Boolean).
In a $t$-local search we permit to flip up to $t$ of
the Boolean variables in the string $y_0$. Let us call the
corresponding local optima $t$-local optima.
So in a $t$-clocal optimum, you cannot improve the value
of the objective function by flipping at most $t$ bits
of $y_0$.
25.54 Bonus (20 points) Consider maximization problems with
$g(n)=n$ and $\Sigma_2=\{0,1\}$ (so $y\in\{0,1\}^n$). Prove:
there exists such a function $f$ such that for every $x$,
1-local search starting from the zero string ($000\dots 0$)
will always find the optimum, but it takes a simply exponential number
of steps to get there. (A "step" means trying a neighboring $y$.)
25.60 Given an instance of the MAX3SAT problem,
we know that in polynomial time we can find an assignment
that satisfies at least a $7/8$ fraction of the clauses.
More to follow. Please check back later.
All exercises are due Fri, Mar 19 at 6pm.
24.05 MATERIAL COVERED.
Coping with $\NP$-completeness: approximation algorithms.
Examples mentioned:
Constant-factor approximation (vertex cover, MAX3SAT),
(fully) polynomial-time approximation scheme (Knapsack).
MAX3SAT approximation resistant. Inapproximability of
MAX-CLIQUE. Holographic proofs/Probabilistically Checkable Proofs (PCPs).
PCP Theorem. Proof of constant-factor inapproximability of MAX-CLIQUE
from PCP Theorem. Interactive proofs. Multi-prover Interactive Proofs:
equivalent to Holographic proofs.
More to follow. Please check back later.
All exercises are due Fri, Mar 19 at 6pm.
This problem set contains the following HW and Bonus problems:
HW 23.64, 23.90, 23.92, 23.99, 23.117, Bonus 23.115, 23.120.
It also includes Challenge problems 23.62, 23.72, 23.110.
23.05 MATERIAL COVERED.
Convex sets, convex hull. Convex polytope: intersection of halfspaces.
Bounded, unbounded. Linear program (LP). Feasibility. Farkas's
Lemma (stated). Duality Theorem (stated). Good characterization.
23.10 STUDY LIN Chap. 5 (Affine and convex combinations)
23.11 CONVENTION: column vectors. A row vector is
a $1\times n$ matrix $(x_1,\dots,x_n)$. A column vector is
the transpose of a row vector: an $n\times 1$ matrix. For
typographical convenience we write a column vector as $x=(x_1,\dots,x_n)^T$.
We shall think of all vectors in $x\in\rrr^n$ as column vectors.
23.12 DEF The Euclidean norm of $x=(x_1,\dots,x_n)^T\in\rrr^n$
is defined as $\|x\|=\sqrt{x^Tx}=\sqrt{\sum_{i=1}^n x_i^2}$.
23.14 DEF The $(n-1)$-dimensional sphere of radius $r > 0$
with center $c\in\rrr^n$ is the subset of $\rrr^n$ defined as
$S^{n-1}(c,r)=\{x\in\rrr^n \mid \|x-c\|=r\}$.
The $n$-dimensional ball of radius $r > 0$
with center $c\in\rrr^n$ is the subset of $\rrr^n$ defined as
$B^n(c,r)=\{x\in\rrr^n \mid \|x-c\|\le r\}$.
23.16 DO Prove: the ball $B^n(c,r)$ is convex.
23.25 DEF For real vectors $x=(x_1,\dots,x_n)^T$ and
$y=(y_1,\dots,y_n)^T$ we say that $x\le y$ if $(\forall i)(x_i\le y_i)$.
23.26 DO Prove: if $a\le b$ and $x\ge 0$ then $a^Tx \le b^Tx$.
(Here $0$ denotes the zero vector $(0,0,\dots,0)\in\rrr^n$.)
23.27 DEF Let $a\in \rrr^n$, $a\neq 0$, and $b\in\rrr$.
The hyperplane $H_{a,b}$ in $\rrr^n$ is defined as
the set $H_a=\{x\in\rrr^n\mid a^Tx=b\}$.
23.28 DEF The hyperplane $H_{a,b}$ defines two half-spaces:
$H_{a,b}^+=\{x\in\rrr^n\mid a^Tx\ge b\}$ and
$H_{a,b}^-=\{x\in\rrr^n\mid a^Tx\le b\}$.
23.29 DO Observe that $H_{a,b}^+ = H_{-a,-b}^-$.
23.32 DEF A polytope in $\rrr^n$ is the intersection
of a finite number of half-spaces. In other words, a polytope
is the set of solutions to a finite set of linear inequalities,
$a_i^T \le b_i$ $(i=1,\dots,k)$, where $a_i\in\rrr^n$ and
$b_i\in\rrr$. ($a_i=0$ is permitted.)
Putting the vectors $a_i^T$ together as the rows of
the $k\times n$ matrix $A$ and writing $b=(b_1,\dots,b_k)^T$, we can
concisely describe the polytope as the set
$$ \{x\in\rrr^n \mid Ax \le b\}\,.$$
23.33 DO Why is permitting zero rows in $A$ compatible with
the definition that the polytope is an intersection of halfspaces
(where $a_i=0$ was not permitted)?
23.34 DO Show that the empty set and the entire
space are polytopes.
23.36 DO Show that every polytope is convex.
23.40 DO Prove that for $n\ge 2$, the $n$-dimensional ball
is not a polytope.
23.42 DEF We say that the hyperplanes $H_{a_1,b_1},\dots,H_{a_k,b_k}$
are in general position if the vectors $a_1,\dots,a_k$ are
linearly independent.
23.44 DO Let $H_1,\dots,H_n$ be $n$ hyperplanes in general
position in $\rrr^n$. Prove that their intersection is a point.
23.46 DEF Let $C\subseteq \rrr^n$ be a convex set. A point
$x\in C$ is an extremum of $C$ if $x$ cannot be written as
$x=(y+z)/2$ for some $x,y\in C$ where $x\neq y$.
23.48 DO Prove that the extrema of the ball $B^n(c,r)$
are the points of the sphere $S^{n-1}(c,r)$.
23.50 DEF A vertex of a polytope is an extremal point.
23.52 DO Prove: every vertex of the polytope $Ax\le b$ in $\rrr^n$
is the intersection of $n$ hyperplanes in general position defined
by $n$ constraints (rows of the list $Ax\le b$ of constraints).
23.54 Observe that a polytope has a finite number of vertices.
23.60 DEF We say that a set $C\subseteq\rrr^n$ is bounded
if $(\exists c\in \rrr^n, r\in\rrr)(C\subseteq B^n(c,r))$.
23.62 CH Every bounded polytope is the convex hull
of its vertices.
23.64 HW (8 points) For every $n$, find a bounded polytope
$P_n\subseteq \rrr^n$ such that the number of constraints
describing $P_n$ grows linearly as a function of $n$ but
the number of vertices of $P_n$ grows simply exponentially.
Describe $P_n$ in terms of $O(n)$ linear inequalities.
State the exact number of inequalities.
Your description should be very simple. State the vertices
of $P_n$ and state their exact number. No proof required,
but the proof should be simple.
23.70 DEF The Linear Programming problem (LP)
takes as input a $k\times n$ real matrix $A$, a "constraint vector"
$b\in \rrr^k$, and an "objective vector" $c\in\rrr^n$ and asks to compute
$$ \sup\{c^Tx \mid Ax \le b\} \,.$$
The $k$ inequalities represented by $Ax\le b$ are the
(linear) constraints
and $c^Tx=c_1x_1+\dots+c_nx_n$ is the (linear) objective function.
23.72 CH Assume the supremum in this definition is finite
(i.e., not $\pm\infty$). Then the supremum is a maximum, i.e.,
$$(\exists x\in\rrr^n)(Ax\le b\text{ and }(\forall z\in\rrr^n)
(Az\le b\Rightarrow c^Tx \ge c^Tz)\,.$$
We say that the supremum is attained by $x$, and
$x$ is an optimal solution to the LP.
23.74 DO If the polytope $Ax\le b$ is non-empty
and bounded then the supremum of the LP defined in 23.70
is attained. (Use the preceding Challenge problem.)
23.78 DEF
The standard form of the LP additionally assumes that $x\ge 0$
(every coordinate of $x$ is non-negative):
$$ \sup\{c^Tx \mid x\ge 0 \text{ and }Ax \le b\} $$
23.80 DO Solving all linear programs and solving standard-form LPs
are computationally equivalent problems. Formalize and prove this statement.
23.82 DEF
A feasible solution of a LP is a vector $x$ that satisfies
the constraints; we ignore the objective function. An LP is feasible
if it has a feasible solution. The LP feasibility problem
asks if a given set of linear constraints, $Ax\le b$, is feasible.
23.84 DO What is the supremum in DEF 23.70 if the LP is infeasible?
23.86 DEF Given the standard-form LP
$\sup\{c^Tx \mid x\ge 0 \text{ and }Ax \le b\} $, to
which we refer as the primal LP, we define the dual LP
as $\min\{b^Ty \mid y\ge 0 \text{ and }A^Ty \ge c\} $.
23.90 HW (Weak Duality Theorem, 8 points) Let $x$ be a feasible solution
of the primal and $y$ a feasible solution of the dual. Prove:
$c^Tx \le b^Ty$.
23.92 HW (Verification of optima, 4 points)
Let $x$ be a feasible
solution of the primal and $y$ a feasible solution of the dual.
Prove: If $c^Tx = b^Ty$ then $x$ is an optimal solution of the
primal and $y$ is an optimal solution of the dual.
23.95 LP Duality Theorem If the primal is feasible
and the primal supremum is finite then the dual is also
feasible then their optima are equal (so $x$ and $y$ as in the
preceding exercise exist).
23.97 DO If both the primal and the dual are feasible
then their optima are equal.
23.99 HW (5 points) Find a feasible primal LP such that
the dual is not feasible. Make your LP as small as possible. (It has
to be standard-form.)
23.102 DO Let $A\in\qqq^{k\times n}$ and $b\in\qqq^k$
be matrices with rational entries. Prove: if the system
$Ax\le b$ is feasible (has a solution in real numbers) then
it is feasible over the rationals (has a solution in rational numbers).
23.104 DO (existence of vertex) Consider the polytope
$\{x\in\rrr^n \mid x\ge 0, Ax\le b\}$. Prove: if this polytope
is not empty then it has a vertex.
23.110 HW (6 points) Let $A\in\rrr^{k\times n}$ and $b\in\rrr^k$.
Assume there exists $y\ge 0$ in in $\rrr^k$ such that $A^Ty=0$ and $y^Tb = -1$.
Prove: the system $Ax\le b$ is infeasible (i.e., the polytope
$\{x\in\rrr^n\mid Ax\le b\}$ is empty).
23.110 CH (Farkas's Lemma) Prove: The system $Ax\le b$ is
infeasible if and only if there exists $y\ge 0$ in in $\rrr^k$ such
that $A^Ty=0$ and $y^Tb = -1$.
23.115 Bonus (18 points)
Consider the LP feasibility problem in the standard form
for integer matrices: the elements of $A$ and $b$ are integers, and the
question is whether the polytope $\{x\ge 0, Ax\le b\}$ is nonempty.
Prove that this problem belongs to $\NP$. What is the witness, and what
is the difficulty with this witness? Use any results stated previously.
23.117 HW (18 points) Prove that the LP feasibility problem
for integer matrices and the same problem in standard form are
Karp equivalent. In other words, you have to prove the Karp
equivalence of the following two decision problems:
It may be helpful to avoid using the same names for the variables in
(B) as in (A), so consider instead the following version of (B). It is
identical to (B) except for the names of the variables.
(B') INPUT: positive integers $\ell, m$,
integer matrices $C\in\rrr^{\ell\times m}$, $d\in \rrr^{\ell}$.
UPDATE (3-17, 10:50pm): version (B') added. Either version (B)
or (B') will be accepted, but version (B') is preferred to avoid
confusion in the notation.
23.120 Bonus (18 points) Prove that the problem stated in 23.115
(LP feasibility in standard form for integer matrices)
belongs to $\NP\cap\coNP$. Use any results stated previously.
More to follow. Please check back later.
All exercises are due Tue, Mar 9, except where stated otherwise.
22.05 MATERIAL COVERED.
MAX3SAT: Two efficient deterministic algorithms to find
$7/8$-satisfying assignment. 1. Method of small sample
spaces for 3-wise independent balanced events. 2. Method
of conditional expectations.
22.10 DEF Let $\Omega=\{a_1,\dots,a_s\}$ be a set of
size $s$ and let $A_1,\dots,A_k \subseteq\Omega$. The
incidence matrix of this list of sets is the
$k\times s$ $(0,1)$-matrix $B=(b_{ij})$ where
The $i$-th row of this matrix is the incidence vector of the
set $A_i$.
22.12 Bonus (25+10 points, due Mar 19) (a)
Prove: for every $k\ge 3$
there exist a uniform probability space and $k$ balanced events
in this space that are 3-wise independent, such that the sample
space has size $\le 4k$.
22.15 HW (3-wise independence method, 18 points)
Use the preceding exercise and exercises from
the previous class to design an efficient algorithm
that takes as input a list of $m$ disjunctive 3-clauses
and finds an assignment that satisfies at least $7m/8$
of them. Let $n$ denote the number of variables.
Your algorithm should run in time $O(n(n+m))$, assuming
the incidence matrix you need from the preceding exercise
is given. (In fact, $O(nm)$ should suffice.)
Justify this running-time bound.
22.20 DEF Let $X$ be a random variable and $B$ an event
with $P(B) > 0$. We define the conditional expectation of $X$,
conditioned on $B$, as
$$E(X\mid B) = \sum_{a\in\Omega} X(a)P(a\mid B)\,.$$
22.22 DO Prove:
$$E(X\mid B) = \frac{1}{P(B)}\sum_{a\in B} X(a)P(a)\,.$$
22.24 DO Prove the following analogue of "Theorem of
Complete Probability" (PROB 7.2.4).
22.26 DO With the notation of the preceding exercise,
$E(X)$ is a weighted average of the $E(X\mid B_i)$. In particular,
$$ \min_i E(X\mid B_i) \le E(X) \le \max E(X\mid B_i)\,.$$
22.30 HW (8 points) Let $C_1,\dots,C_m$ be a list disjunctive clauses.
(Repetition is permitted.)
Let $C_j$ be the disjunction of $k_j$ literals, corresponding
to $k_j$ distinct variables. (So no variable can appear in
two literals in $C_j$.) Let us consider a random assignment
$u=(u_1,\dots,u_n)$ of $(0,1)$ values to the variables:
$x:=u\in\{0,1\}^n$. Let $X=|\{j\mid C_j(u)=1\}|$ denote the
number of clauses $C_j$ satisfied under this assignment.
Express $E(X)$ in terms of $m$ and the $k_j$. Give a simple (but not
closed-form) expression that is easy to evaluate.
22.32 DEF Let $f=f(x_1,\dots,x_n)$ be a Boolean function.
A partial assignment of Boolean values to the variables
is an assignment of Boolean values to some of the variables;
the resulting function depends on the remaining (unassigned)
variables. Let $I\subseteq [n]$ and let $u: I\to \{0,1\}$
be an assignment of Boolean values to $I$. We write $f^u$ to denote
the function in which $x_i$ has been assigned the value $u(i)$.
So $f^u$ is a function of the variables $\{x_j\mid j\in [n]\setminus I\}$.
We call $f^u$ a restriction of $f$.
22.34 DO Let us say that $C$ is a disjunctive$^*$ clause if
either $C$ is a disjunctive clause or $C$ is the constant $1$.
(Note that the constant $0$ is the empty disjunctive clause,
i.e., the OR of the empty set of literals.) Observe that for any
partial assignment $u$, the function $C^u$ is also a disjunctive$^*$
clause.
22.40 Method of Conditional Expectations.
We need some notation to formalize this algorithm.
For a Boolean function $f=f(x_1,\dots,x_n)$, $\ell\in [n]$,
and $\epsilon\in\{0,1\}$, let $f^{\ell,\epsilon}$ denote
the restriction of $f$ after the assignment $x_{\ell}:=\epsilon$.
INPUT: a list $C_1,\dots,C_m$ of disjunctive$^*$ clauses.
$D_j$ will denote the restriction of the clause $C_j$ after the
current partial assignment.
Initialization
22.42 HW (4 points) Justify the comment in line 08.
22.44 DO Prove the correctness of the algorithm: show that
the assignment $u$ returned satisfies at least the expected number
of satisfied clauses. What is your loop invariant?
22.46 HW (15 points)
Let the input be a list of $m$ disjunctive 3-clauses in $n$ variables.
Find an upper bound on the complexity of the algorithm
in terms of $n$ and $m$. Get the best upper bound you can. Do not use
the unit cost model; instead, use the bit-model: comparison, arithmetic
of $N$-bit integers costs $O(N)$. Clearly state and analyze
each item of cost. Assume that on line 05 we always pick the next integer.
22.70 HW (7+8 points) (a) Given a graph $G$,
the minimum vertex cover problem seeks to find the value $\tau(G)$.
State the decision version of this optimization problem.
You need to make two statements: What is the INPUT and what
is the (YES/NO) QUESTION.
Clarity is paramount. No justification is required.
(b) Let COVER denote the language corresponding to the
decision problem described in part (a). Define
the CLQUE language (INPUT, QUESTION). Prove that COVER is
$\NP$-complete, by Karp-reduction from the CLIQUE language.
22.73 HW (12 points) Prove that there is a linear-time
factor-2 approximation algorithm for the minimum cover problem for graphs.
Your input is a graph $G=(V,E)$. You need to return a set $W\subseteq V$
such that $W$ is a cover (hits every edge) and $|W|\le 2\tau(G)$.
Prove the correctness of your algorithm and justify the runnig time.
As always, you may refer to previous exercises. No pseudocode required.
22.80 Bonus (15 points, due Mar 19)
Let $f: \nnn\to\nnn$ be an increasing
function, where $\nnn$ denotes the set of positive integers.
Assume $f(2n) \le 2 f(n)+O(n^2)$ $(n\in\nnn)$. Give the best asymptotic
upper bound you can for $f$ based on this information.
Your answer should be of the form $f(n)=O(g(n))$ where $g$ is given
by a very simple formula.
Prove that your $g(n)$ is best possible, up to a constant factor.
All exercises are due Tue, Mar 9, except where stated otherwise.
21.05 MATERIAL COVERED.
Random variables. Expected value. Linearity of expectation.
Indicator variables. Counting events via indicator variables.
NP-hardness. NP-hard optimization problems. MAX3SAT.
Out of $m$ 3CNF clauses, at least $7m/8$ are simultaneously
satisfiable. Does this lead to a $7/8$-approximation
algorithm?
21.10 STUDY PROB Sec. 7.7 (Random variables, expected value,
indicator variables)
21.15 DO Solve the following exercises in PROB Sec 7.7:
7.73 (Alternative definition of the expected value),
7.75 ($\min X \le E(X) \le \max X), 7.77
(linearity of expectation), 7.710 (bijection between events
and indicator variables), 7.711 (expected value of indicator variable),
7.714 (Markov's Inequality)
21.18 WORKED EXAMPLE. Let $A_1,\dots,A_k$ be events. Let $X$
count those events that actually occur. Prove: $E(X)=\sum_{i=1}^k P(A_i)$.
21.20 WARNING. Events have probability; random variables
have expected value. Events do not have expected value,
and random variables do not have probability.
21.22 DO Let us flip $n$ biased coins; coin #$i$
has probability $p_i$ of coming up Heads. Determine the expected
number of Heads.
21.25 HW (12 points) PROB 7.7.15 (a) (expected number of
Aces in poker hand). Conceptual clarity is paramount.
21.28 Bonus (18 points) PROB 7.7.18 (Club of 2000).
Conceptual clarity is paramount.
21.30 DEF Let $\pi : D\to D$ be a permutation of the set $D$.
For $x\in D$, let $C(x,\pi)$ denote the cycle of $x$ under $\pi$,
this is the cyclic sequence $(x, \pi(x), \pi^2(x),\dots,\pi^{p-1}(x)$
where $p$ is the smallest positive integer such that $\pi^{p}=x$.
The value $p$ depends on $x$ and $\pi$, so we write $p=p(x,\pi)$.
We call $p(x,\pi)$ the period of $x$ under $\pi$. We say that
$x$ is a fixed point of $\pi$ if $\pi$ fixes $x$, i.e., if
$p(x,\pi)=1$.
21.32 DO Let $S_n$ denote the set of permutations of $[n]$.
Fix $x\in [n]$. Pick a random permutation $\pi\in S_n$. (So,
by DEF 10.39, every permutation has probability $1/n!$ to be chosen.
The sample space for this experiment is $\Omega = S_n$ and the
probability distribution is uniform.)
Prove: the probability that $\pi$ fixes $x$ is $1/n$.
21.34 HW (8 points) Determine the expected number of fixed
points of a random permutation $\pi\in S_n$.
21.36 Bonus (10 points) A permutation is fixed-point-free
if it has no fixed points. Let $p_n$ denote the probability that a
ranodm permutation from $S_n$ is fixed-point-free. Prove:
$\lim_{n\to\infty} p_n = 1/\eee$.
21.40 DO Let $\pi\in S_n$ be a random permutation.
Let $1\le k\le n$. Fix $x\in [n]$. Prove: $P(p(x,\pi)=k)=1/n.$
21.45 Bonus (15 points) Let us pick $\pi\in S_n$ at random.
Let $X_n$ denote the number of cycles of $\pi$ (including
the fixed points because they are the cycles of length 1).
Prove: $E(X_n)\sim \ln n$.
21.50 DEF A disjunctive 3-clause is an OR of 3 literals.
The MAX3SAT problem takes as input a list of
disjunctive 3-clauses, and asks the maximum number that can be
simultaneously satisfied.
21.53 DO Let $T$ be a list of $m$ disjunction 3-clauses
in the Boolean variables $x_1,\dots,x_n$. Let us assign
Boolean values (zeros and ones) at random for our variables
(by flipping $n$ independent unbiased coins). So the sample
space for this experiment has size $2^n$. Let $X$ denote
the number of clauses on our list that are satisfied by the
random assignment. Prove: $E(X) = 7m/8$.
21.55 DO (a) Prove: given a list of $m$ 3-clauses,
at least $7m/8$ of them can be simultaneously satisfied.
(b) Prove that this bound is tight for every $m$ that is divisible by $8$.
21.60 CH Pick $x\in [n]$ at random. Let $X_n$ denote the number
of distinct prime factors of $x$. Prove: $E(X_n)\sim \ln\ln n$.
More to follow. Please check back later.
Karp reduction. NP-completeness. Cook-Levin Theorem:
SAT is NP-complete. The P $\neq$ NP conjecture.
Reducing SAT to the case of fan-in 2 gates.
Reducing this case to 3SAT. The CLIQUE language.
The Independent Set language, their Karp equivalence.
NP-completeness of CLIQUE by reduction from 3SAT.
Other NP-complete languages.
More to follow. Please check back later.
19.05 STUDY the entire "Computability and Complexity" handout (COMP).
This handout expands the previous "Computability" handout.
19.10 DO Solve all exercises in COMP.
19.15 HW (20 points) COMP 5.3
(Fibonacci numbers mod $m$ in polynomial time)
19.18 HW (3 points)
Does the problem of computing the determinant of
an integral matrix (matrix with integer entries) belong to $\calP$ ?
Reason your answer.
19.20 HW (12 points) Show that the dynamic programming
solution of the integer Knapsack problem requires exponential time.
For the proof, you need to construct a class of inputs that
force the algorithm to take $\exp(\Omega(N^c))$ time, where
$N$ is the bitlength of the input and $c$ is a positive constant.
Find the largest value of $c$ for which you can construct such input.
Consider only those inputs where $W$ (the weight limit)
is less than the sum of all weights. (Otherwise the
problem is trivial.)
19.22 HW (10 points) COMP 6.8 (Factoring is Cook equivalent
to the FACT language)
19.25 HW (10 points) COMP 7.7 $(\calP \subseteq\NP)$
19.30 HW (8 points, due Mar 9) COMP 7.10
(which conjecture follows from the other? - Prove your answer)
19.35 Bonus (15 points) COMP 7.14 $(\FACT \in\coNP)$
19.37 CH COMP 7.15 $(\FACT \in\coNP$ without AKS)
19.39 HW (6 points) COMP 7.17 (Conj fails
$\Rightarrow$ RSA broken). You may use previous exercises in COMP.
19.45 HW (12 points) COMP 8.4 (Karp reducibility transitive)
19.48 HW (10 points) COMP 8.6 (non-3-colorability is
Karp reducible to $\HALTING$)
19.50 HW (18 points) COMP 8.7 (3COL Karp reducible to 4COL)
19.55 DO COMP 8.10 $(\NPC\cap \calP=\emptyset)$
19.57 Bonus (10 points) COMP 8.11 $(\NPC\cap \coNP=\emptyset)$
19.60 HW (14 points, due Mar 9) COMP 8.13
(if $\SAT \prec_{\karp} \FACT$ then $\dots$).
Your proof shoud be very simple, by combining some of
the earlier exercises in COMP.
19.62 Bonus (28 points, due Mar 19) COMP 8.14
(if $\SAT \prec_{\cook} \FACT$ then $\dots$).
Your solution to this problem will not earn you
credit for 19.60. Give a simple proof for 19.60.
18.05 STUDY the "Computability and Complexity" handout (COMP),
Sections 1-4. Solve the exercises in these sections.
This handout is an expanded version of the previous "Computability" handout;
Section 1-4 are identical with the previous handout.
18.10 DO COMP 1.4, 1.5, 3.4, 3.5.
18.15 HW (8 points) COMP 3.9 (3COL $\in\calR)$)
18.17 HW (12 points) COMP 3.11
(characterisation of computably enumerable languages)
18.19 HW (10 points) COMP 3.12 $(\calR\subseteq\RE)$
18.21 HW (6 points) COMP 3.13 $(\calR\subseteq\RE\cap\coRE)$
18.23 Bonus (14 points) COMP 3.14 $(\calR =\RE\cap\coRE)$
18.25 HW (7 points) COMP 4.1 (HALTING $\in\RE)$
18.27 HW (7 points) Prove: HALTING $\notin\coRE$
18.29 DO Infer from the previous exercise that (a) $\RE\neq \calR$
and (b) $\RE\neq\coRE$.
More to follow. Please check back later.
17.05 STUDY the "Repeated squaring" handout.
17.10 DEF PRIMALITY is the decision problem that takes as
input an integer $x\ge 2$ and answers YES if $x$ is a prime number,
NO otherwise. FACTORING is the problem that takes as input
an integer $\ge 2$ and finds a nontrivial divisor of $x$, i.e.,
an integer $d$ in the range $2\le d \le x-1$ such that $d\mid x$,
if such a $d$ exists; otherwise returns "prime."
17.12 COMMENT These two problems should not be confused.
While FACTORING will decide PRIMALITY, FACTORING is perceived as
a hard problem whereas PRIMALITY is "easy." Specifically,
the best known algorithm for FACTORING runs in time
$\exp(O(\sqrt{n \log n})$ where $n$ is the number of digits of
the smallest prime factor of $x$, while PRIMALITY can be decided
in polynomial time. The perception that the RSA cryptosystem, widely
used in ecommerce, is secure, requires the assumption that the FACTORING
problem has no efficient solution. Notably, this assumption fails
in quantum computing: the celebrated result of Peter Shor (1994)
states that FACTORING can be solved in quantum polynomial time.
This result triggered the rise of the new area of post-quantum
cryptography, the design of cryptographic schemes that may
be secure against quantum computers.
17.14 DEF A composite number is an integer $\ge 2$
that is not prime.
17.16 Witnesses of compositeness. The definition offers a
type of witness of compositeness: a nontrivial divisor. However,
finding such a witness is equivalent to FACTORING, so we need to
look for easier-to-find witnesses of compositeness. Such witnesses
exist and are based on Fermat's little Theorem.
17.20 Fermat's little Theorem. Let $p$ be a prime number
and $a$ an integer. If $\gcd(a,p)=1$ then $a^{\,p-1}\equiv 1\pmod p$.
17.22 DEF We say that the integer $a$ is a Fermat witness
of compositeness of the positive integer $x$ if $\gcd(x,a)=1$ and
$a^{x-1}\not\equiv 1 \pmod x$. We say that such an $a$ is a
Fermat witness for $x$.
17.24 DO Prove: If the positive integer $x$ has a Fermat witness
then $x$ is a composite number.
17.26 The converse is not true: not all composite numbers have
Fermat witnesses.
17.28 DEF The positive integer $x$ is a Carmichael number
if $x$ is composite but has no Fermat witness. In other words,
a Carmichael number is a composite number that satisfies Fermat's little
Theorem: for every integer $a$, if $\gcd(a,x)=1$ then
$a^{x-1}\equiv 1 \pmod x$.
17.30 Bonus (8 points) Prove that $561=3\cdot 11\cdot 17$
is a Carmichael number. (Note: this is the smallest Carmichael number.
Do not prove that it is the smallest.)
17.32 READ Wikipedia's item on Carmichael numbers. It is known
that there are infinitely many Carmichael numbers, but it is believed
that they are much less frequent than prime numbers.
17.35 Bonus (15 points)
Let $x\ge 2$. Let us say that $a$ is a simple
witness of compositeness of $x$ if $x\nmid a$ and
$a^{x-1}\not\equiv 1\pmod x$. Let us pick $a\in [x-1]$ at random.
Prove: if $x$ is not a prime nor a Carmichael number then
$P(a$ is a simple witness of compositeness for $x)\ge 1/2$.
17.37 ALGORITHM. Input: $x\ge 2$.
Repeating the experiment of picking $a\in [x-1]$
independently $t$ times. If at least one of these trial turns
up a simple Fermat witness then return "composite," otherwise
return "prime of Carmichael."
17.39 DO Prove: The probability that the algorithm returns
a wrong answer is $\le 2^{-t}$.
17.43 Enhanced witnesses lead to primality testing. One of these
is the Miller--Rabin test. We may assume $x$ is odd.
17.45 DEF Miller witness Input: $x\ge 2$, odd.
01
If $a^{x-1}\not\equiv 1 \pmod x$
then return YES
(Note, in case what you see on your browser is ambiguous:
17.47 Bonus (15 points) Prove: if $x$ is a prime number then
$x$ has no Miller witness.
17.49 CH Prove: If $x$ is odd and composite then
there exists a Miller witness that is relatively prime to $x$.
17.51 CH Let $x$ be odd and $x\ge 3$. Prove: If there exists
a Miller witness for $x$ that is relatively prime to $x$ then
$P(a\in [x-1]$ is a Miller witness$)\ge 1/2$.
17.53 DO (Miller--Rabin primality test) (1977).
Combine the preceding
three exercises to an algorithm that will, on any odd input $x\ > 2$,
declare "prime" or "composite". If $x$ is a prime, the
answer will always be correct; if $x$ is composite, the answer will
be correct with high probability. (So if the algorithm returns "prime,"
there is a small chance that this answer is wrong, but if it returns
"composite," this will come with a proof, namely, a Miller witness.)
17.55 Another famous randomized primality test is the
Solovay-Strassen primality test (1977). Its efficiency
is similar to the Miller-Rabin test. The algorithm is based
on the Law of Quadratic Reciprocity, one of the results of which
Gauss was most proud (invented five proofs of it over a period
of decades). You can read about quadratic reciprocity and
the Solovay-Strassen test in Wikipedia.
17.60 The AKS primality test. In 2002, Agrawal, Kayal, and
Saxena announced a deterministic polynomial-time primality test.
This breakthough was rewarded by multiple awards.
17.62 NOTATION For a positive integer $m$
and an integer $a$ we write $z=(a \bmod m)$ to denote the smallest
nonnegative residue of $a$ modulo $m$. In other words, $z$ is
uniquely defined by the constraints $z\equiv a\pmod m$ and
$0\le z\le m-1$.
17.65 Modular exponentiation. Given the integer $a$ and the
positive integers $b,m$, we wish to compute $(a^b \bmod m)$ in time,
polynomially bounded in the length of the input. This can be
done using the method of repeated squaring. STUDY the
handout "Repeated squaring" and pay special attention to
the elegance of the loop invariant.
17.67 The RSA cryptosystem is based on Fermat's little Theorem.
Efficient modular exponentiation is required for the Fermat test
and all algorithms mentioned, including the RSA cryptosystem, so
Fermat's little Theorem and the repeated squaring algorithm
play a critical role in a multi-trillion-dollar industry.
The elegance of both the theorem and the algorithm are
also noteworthy, and contributes to their success.
More to follow. Please check back later.
16.10 STUDY LinAlg, Section 6.3 ("Determinant vs. nonsingularity
and rank"). This is a newly inserted section (Feb 17, 2021). If what you
see as Section 6.3 has a different title, please clear your browser's
cache and try again.
16.12 REVIEW LinAlg, Section 6.2.
16.20 HW (9 points) Let $G$ be a bipartite graph and let $B$ denote
its modified incidence matrix (the 1s are replaced by distinct variables).
Prove: $\nu(G) = \rk(B)$. Specifically cite the results from
LinAlg you are using.
16.22 NOTATION Note that the number of variables in $B$ is $m$,
the number of edges. Let us label them as $x_1,\dots,x_m$.
16.24 HW (8 points) Let $\ul\alpha=(\alpha_1,\dots, \alpha_m)$
be a list of $m$ scalars. Prove:
$\rk B(\ul\alpha) \le \rk(B)$.
16.26 TERMINOLOGY Let $U$ be a non-empty finite set.
If we say we pick an element of $U$ "uniformly at random," we mean
a collection of events $E_u$ $(u\in U)$ that are pairwise disjoint,
$\bigcup_{u\in U} E_u=\Omega$ (so the $E_u$ partition $\Omega$),
and $(\forall u\in U)(P(E_u)=1/|U|)$.
If $E_u$ occurs we say that we "picked $u$."
16.28 HW (10 points) Let $S$ be a finite set of scalars: $|S|=N$.
Prove: If $\ul\alpha=(\alpha_1,\dots,\alpha_m)$ is selected
uniformly at random from $S^n=S\times S\times\dots\times S$
then $P(\rk(B(\ul\alpha)) < \rk(B)) \le \min(a,b)/N$,
where $a$ and $b$ are the sizes of the two parts of $G$ and
$\ul\alpha=(\alpha_1,\dots,\alpha_m)$.
16.30 HW (16 points) Describe the randomized algorithm
discussed in class to find $\nu(G)$ for a given bipartite graph $G$
with parts of size $a$ and $b$. Use as the primitive the calculation
of the rank of an $a\times b$ matrix of scalars. In other words,
your complexity measure will be the number of times you need to
calculate such a rank. Use the value $N = 2\min(a,b)$.
You are also given a value $\epsilon > 0$, and your algorithm
must have error probability $\le \epsilon$. State, how many
times you need to calculate rank. Prove your probability
estimate.
16.40 DEF The adjacency matrix of a digraph $G=([n],E)$
is an $n\times n$ matrix $A=(a_{ij})$ where $a_{ij}=1$ if $(i,j)\in E$
and $a_{ij}=0$ otherwise.
16.42 DO $G$ is a graph (undirected) if and only if
$A$ is a symmetric matrix: $A^T=A$ where $A^T$ denotes the transpose,
and all diagonal elements $a_{ii}$ are zero (we did not permit self-loops
in an undirected graph).
16.44 DEF The Tutte matrix of a graph $G$ is a modified
version of the adjacency matrix: we replace each entry of 1 by a variable
$x_{ij}$ such that $x_{ji}=-x_{ij}$; distinct edges correspond to distinct
variables.
So the number of distinct variables is $m$, the number of (undirected) edges.
16.46 DO The Tutte matrix $C$ is a skew symmetric matrix:
$C^T = -C$.
16.48 HW (6 points) Let $C$ be a skew symmetric $n\times n$ matrix
over $\rrr$. Prove: if $\det C\neq 0$ then $n$ is even. The
proof should be no more than two lines.
16.50 Theorem Let $C$ be the Tutte matrix of the graph $G$.
$G$ has a perfect matching if and only if $\det C \neq 0$.
16.52 Bonus (20 points) Prove the Theorem.
16.60 DFS review based on "Introduction to Algorithms"
by Cormen, Leiserson, Rivest, and Stein.
16.65 Parenthesis Theorem Let $u, v\in V$ be vertices.
Assume $d_u < d_v$. Then exactly one of the following
cases occurs:
16.67 DO Prove the Parenthesis Theorem.
16.69 DO (nesting descendants' intervals)
$v$ is a descendant of $u$ if and only if $d_u\le d_v\le f_v\le f_u$.
16.72 White Path Theorem $v$ is a decendant of $u$ if and only if
at time $d_u$ there is a white path from $u$ to $v$ (a path, each vertex
of which is $\white$).
16.74 HW (8 points) Prove the White Path Theorem.
16.80 HW (8 points) Compute the $n$-th power of the matrix
$H = \begin{pmatrix} 1 & 1 \\
1 & 0 \end{pmatrix}$.
16.85 HW (8 points) "Edit-distance" handout.
16.90 DEF A Boolean variable takes values 0 or 1. A Boolean
function in $n$ variables is a function $f(x_1,\dots,x_n)$
of $n$ Boolean variables that takes values 0 or 1, so
we can write $f : \{0,1\}^n \to \{0,1\}$.
16.92 HW (7 points, due Mar 2)
Count the Boolean functions in $n$ variables.
Your answer should be a very simple formula.
Briefly reason your answer.
16.95 DEF A Boolean circuit is a DAG with special
labeling on the "gates" (nodes) and the "wires" (edges).
There are $n$ input gates, labeled by the $n$ variables; these nodes
are the sources of the DAG (nodes of in-degree zero). All other gates are
labeled by the Boolean operator symbols $\wedge$ ("AND") and $\vee$ ("OR")
(AND-gates and OR-gates). A nonempty subset of the nodes is designated
as output gates. The children of a gate are its
in-neighbors; the parents of a gate are its out-neighbors.
We assume that every gate that is not an input gate has at least
one child. Some of the wires are labeled $\neg$ ("NEGATION").
16.96 DEF We say that the Boolean circuit $B$ represents
the Boolean function $f$ is $B$ has an output gate that computes $f$.
16.97 DEF The size of a Boolean circuit is the
number of wires.
16.98 DEF The depth of a Boolean circuit is
the length of the longest path from an input gate to an output gate.
16.105 DEF A literal is a Boolean variable $x_i$ or
its negation $\xbar_i=1-x_i$.
16.107 DEF Pushing all negations to the input level.
In a modified Boolean circuit, there are $2n$ input gates,
one for each literal, and there are no negations on the wires.
16.109 DO (De Morgan's laws) If $f$ and $g$ are Boolean
functions then
(a) $\overline{f \vee g}={\overline f} \wedge {\overline g}$
(b) $\overline{f \wedge g}={\overline f} \vee {\overline g}$
16.112 Bonus (15 points, due Mar 2)
Prove: every Boolean circuit can be simulated by
a modified Boolean circuit without significant increase in size
(at most a factor of 2) and no increase in depth. "Simulation"
means they compute the same Boolean functions.
("Size" means the number of wires, DEF 16.97)
(Hint: DeMorgan's laws.)
16.115 DEF A disjunctive clause is an
OR of literals, e.g., $x_3 \vee \xbar_7 \vee \xbar_8 \vee x_{10}$.
A CNF (Conjunctive Normal Form) is an AND of disjunctive clauses:
$C_1 \wedge \dots \wedge C_m$ where the $C_i$ are disjunctive clauses.
Analogously, a conjunctive clause is an AND of literals,
and a DNF (Disjunctive Normal Form) is an OR of conjunctive clauses.
16.116 OBSERVE that CNFs and DNFs are Boolean circuits of depth 2.
16.118 HW (12 points, due Mar 2)
(a) Prove: every Boolean function is representable by a DNF.
(b) Prove: every Boolean function is representable by a CNF.
16.125 DEF (PARITY function)
For Boolean variables $x_1,\dots,x_n$
we write $\parity_n(x_1,\dots,x_n):= \sum_{i=1}^n x_i \pmod 2$.
This function is also denoted $x_1\oplus x_2\oplus\dots\oplus x_n$.
16.127 DO Find a CNF and a DNF for $x\oplus y$.
16.130 Bonus (12 points, due Mar 2)
Prove: if we represent $\parity_n$ as a CNF then the expression
will have at least $2^{n-1}$ disjunctive clauses.
16.135 Bonus (18 points, due Mar 2) Prove: $\parity_n$ can be
represented by a depth-3 Boolean circuit of size $2^{O(\sqrt{n})}$.
More to follow. Please check back later.
15.04 STUDY "Finite Probability Spaces" (PROB), Section 7.4
(Independence of multiple events)
15.12 DEF We say that an event is balanced if its
probability is $1/2$.
15.12 HW (5 points) PROB 7.4.5(b) (independence of union
for 3 events)
15.16 HW (3+6 points) PROB 7.4.7 (pairwise independence
does not imply independence for 3 events)
15.18 Bonus (6 points) PROB 7.4.8(b) (three balanced events
that multiply but are not independent)
15.20 HW (5+4 points) (a) PROB 7.4.16 (independence of
complement) (b) PROB 7.4.17 (independence of complements).
(For 3+2 points credit, solve for $k=3$ events)
15.22 Bonus (8 points) PROB 7.4.18 ($k$ independent nontrivial
events require sample space of size $\ge 2^k$). (For 4 points credit,
solve for $k=3$.)
15.24 Bonus (15 points) PROB 7.4.19 ($n$ balanced events
that are $(n-1)$-wise independent but not fully independent). Minimize
the sample space; prove that your sample space is as small as possible.
Your construction should be short and easy to analyze. Elegance matters.
(For 7 points credit, solve for $n=3$ events.)
15.26 Bonus (18+18 points) PROB 7.4.20 (a)(b) (small
sample space for pairwise independent events)
15.28 CH PROB 7.4.22 (lower bound for pairwise
independent events)
15.30 DO PROB 7.4.24 (independence of Boolean combinations).
While this is just a "DO" exercise, I mean it: you need to thoroughly
understand this problem.
15.32 DO PROB 7.4.24 (trick problem -- the solution is fun)
15.40 Polynomial Identity Lemma Let $f(x_1,\dots,x_n)$
be a polynomial in $n$ variables. Assume $\deg(f)\le d$.
Let $S$ be a set of scalars, $|S|=N$. Let
$\ul\alpha=(\alpha_1,\dots,\alpha_n)$ where each $\alpha_i$
is selected from $S$ uniformly at random. In other words,
for every $\beta_1,\dots,\beta_n\in S$, we have
$P((\forall i)(\alpha_i=\beta_i))= N^{-n}$.
15.42 HW (18 points) Reconstruct the proof of the Polynomial Identity
Lemma from the class notes.
More to follow. Please check back later.
14.04 STUDY "Finite Probability Spaces" (PROB), Sections 7.1 (events),
7.2 (conditional probability), 7.3 (Independence, positive/negative
correlation)
14.07 STUDY LinAlg, Section 11.2 (multivariate polynomials)
14.10 Bonus (8 points)
Find the dimension of the space of polynomials
of degree $\le d$ in $n$ variables. Your answer should be a very
simple closed-form expression (no summation or product symbols, no
dot-dot-dots) involving a binomial coefficient. Prove your answer.
For half credit, solve this problem for $n=3$.
14.12 HW (6 points) Let $f,g$ be multivariate polynomials.
Prove: $\deg(fg)=\deg(f)+\deg(g)$. (Read the definitions in LinAlg,
Section 11.2, carefully.)
14.20 HW (4 points) PROB 7.1.3 (number of trivial events)
14.22 HW (4 points) PROB 7.1.6(a) (biased coin flips).
What you need to show is that the numbers
14.24 Bonus (7 points, due Feb 23)
PROB 7.1.6(c4) (even number of Heads)
14.26 Bonus (4+5+2 points, due Feb 23)
PROB 7.2.5 (a)(b)(c) (probability of causes)
Give your answers as exact fractions, not decimals. Show all your work,
including all intermediate results.
14.28 HW (4 points) Let $A, B$ be events. Assume $P(B) < 1$.
Prove: $P(A) \le P(B) + P(A\mid \Bbar)$, where
$\Bbar = \Omega\setminus B$ is the complement of $B$.
State why we needed the assumption that $P(B) < 1$.
14.30 Bonus (8 points, due Feb 23) PROB 7.3.11 (correlation of
divisibility by 2 and 3)
14.35 CH (strongly negatively correlated events) PROB 7.8.22(a)
14.40 DEF A Hamilton cycle in a graph is a cycle of
length $n$, i.e., a cycle that passes through every vertex.
A graph is Hamiltonian if it has a Hamilton cycle.
14.42 DEF A decision problem has a YES/NO answer.
The Hamiltonicity decision problem asks whether a given graph
is Hamiltonian.
14.43 DEF A search problem asks to find an object
with a given property if one exists. The Hamilton cycle search
problem asks to find a Hamilton cycle in a given graph if
the graph is Hamiltonian.
14.45 HW (decision vs. search, 12 points, due Feb 23)
Imagine that we have a
"Hamiltonicity oracle": a machine that takes a graph as input and
answers YES or NO depending on whether the graph is Hamiltonian.
An "oracle algorithm" with respect to this oracle is permitted
to compute graphs and serve them as inputs to the oracle.
The oracle queries are free. Give a polynomial-time oracle algorithm
with respect to this oracle that finds a Hamilton cycle
in the input graph if one exists. In other words, solve
the Hamilton cycle search problem with the help of an oracle for
the Hamiltonicity decision problem.
13.05 STUDY LinAlg Chapters 3, 4, 6 and 7 (matrix rank, systems
of linear equations, determinants, Cramer's Rule)
13.20 DEF Let $x=(x_1,\dots,x_n)$ be a real or complex vector.
The $\ell_1$-norm of a $x$ is $\|x\|_1=\sum_{i=1}^n |x_i|$.
The $\ell_2$-norm (Euclidean norm)
of $x$ is $\|x\|_2=\sqrt{\sum_{i=1}^n |x_i|^2}$.
The $\ell_{\infty}$-norm ("max-norm") of $x$ is $\|x\|_{\infty}=\max_i |x_i|$.
13.25 HW (4 points)
Let $a_1,\dots,a_n$ be the rows of the $n\times n$
real matrix $A$. Prove: $|\det(A)|\le\prod_{i=1}^n \|a_i\|_1$.
13.27 CH (previous exercise continued)
Prove: $|\det(A)|\le\prod_{i=1}^n \|a_i\|_2$.
13.29 CH ((0,1)-matrices with large determinants)
The preceding exercise shows that the determinant of an
$n\times n$ $(0,1)$-matrix is less than $n^{n/2}$.
Find an infinite family of $(0,1)$-matrices with
determinant greater than $(n/2)^{n/2}$.
13.32 HW (6 points) Let $A=(a_{ij})$ be an integer matrix.
Define the bitlength of $A$ as the sum of the bitlengths
of its entries: $b(A)=\sum_i\sum_j \lceil \log_2 (|a_{ij}|+1)\rceil$.
Prove: $b(|\det(A)|) \le b(A)$.
13.50 DO Let $A$ be the $n\times n$ incidence matrix
of the bipartite graph $G$ with $n$ vertices in each part.
Prove: If $\det(G)\neq 0$ then $G$ has a perfect matching.
More to follow. Please check back later.
12.10 DEF Let $x_1,\dots,x_n$ be real numbers. The
arithmetic mean of these numbers is defined as
$$ A(x_1,\dots,x_n)=\frac{1}{n}\sum_{i=1}^n x_i .$$
Assume now that $x_1,\dots,x_n > 0$. The geometric mean
of these numbers is
$$ G(x_1,\dots,x_n)=\left(\prod_{i=1}^n x_i\right)^{1/n}.$$
12.12 DO$^*$ Let $x_1,\dots,x_n > 0$ be real numbers.
Prove: $A(x_1,\dots,x_n)\ge G(x_1,\dots,x_n)$.
Moreover, equality holds if and only if $x_1=\dots=x_n$.
12.15 Recall that by "graph" we mean an undirected graph.
12.17 HW (10 points)
For every even value of $n$ find a graph with
$n$ vertices, and two vertices, $s$ and $t$, in $G$ such that
there are at least $2^{(n-2)/2}$
shortest $s-t$ paths in $G$. The description of your graphs should be
simple; solutions with a complicated description will not be evaluated.
It helps if you attach an illustration with $n=10$. Hand drawing is ok.
State the length of the shortest $s-t$ paths and briefly reason
why the number of shortest $s-t$ paths is right.
12.19 CH Let $G$ be a graph and $s$ and $t$ two vertices.
Prove that the number of shortest $s-t$ paths in $G$
is less than $\eee^{(n-1)/\eee}$.
12.22 Bonus (14 points, due Feb 23)
Let $G=(V,E)$ be a graph and $s$ a vertex.
For each $w\in V(G)$, count the shortest
$s-w$ paths. Your algorithm should
run in linear time in the unit cost model where operations
on $O(n)$-digit numbers (addition, copying) are done at unit cost.
12.30 STUDY the "Greedy matching" (GRMATCH) handout. The matching
number is denoted $\nu(G)$, in LaTeX $\tt \backslash \nu(G)$.)
($\nu$ is the Greek letter "nu"). Note that the greedy matching
algorithm always finds a maximal matching, but not necessarily a
maximum matching.
12.32 HW (6 points) Given a graph $G=([n],E)$
in edge-list representation,
implement the greedy matching algorithm in linear time. The edges
must be selected in the order given in the edge list. Write a
simple pseudocode. Explain. No analysis required.
12.34 Bonus (7 points, due Feb 23)
Determine the number of matchings in the path $P_n$
with $n$ vertices. Your answer should be a very simple expression in terms
of a familar sequence. Prove your answer.
12.36 DO Verify: $\nu(P_n)=\nu(C_n)=\nu(K_n)=\lfloor n/2\rfloor$.
For the complete bipartite graph $K_{r,s}$ we have $\nu(K_{r,s})=\min(r,s)$.
12.38 HW (maximal vs. maximum matching, 7 points)
Let $M$ be a maximal matching in $G$. Prove:
$|M|\le \nu(G)\le 2|M|$.
12.40 HW (5 points) Prove that the upper bound in the preceding
exercise is tight for every even value of $\nu$.
In other words, for every $k\ge 0$ you need to
construct a graph $G$ such that $\nu(G)=2k$ and $G$ has a maximal
matching of size $k$.
12.42 DO Count the maximum matchings is $P_n$.
12.44 DO The outcome of the greedy matching algorithm
depends on the order in which the edges are listed. Let us apply
the greedy matching algorithm to the path $P_n$ under a random ordering
of the $n-1$ edges. Prove that the probability that the matching we get
is maximum is simply exponentially small, i.e., it is less than $c^{-n}$ for
some constant $c > 1$ for all sufficiently large $n$. (Use the naive
notion of probability: number of good cases divided by the number of
all cases.)
12.50 DEF A vertex cover of the graph $G=(V,E)$
is a subset $T\subseteq V$
such that every edge includes at least one vertex from $T$. In other
words, $T$ "hits" every edge. The covering number of $G$
is the minimum size of its vertex covers; it is denoted by
$\tau(G)$. (The LaTeX code of the Greek letter $\tau$ is
$\tt \backslash tau$.) A vertex cover of size $\tau(G)$ os called
a minimum cover
A vertex cover is also called a hitting set.
12.52 DO Verify: $\tau(P_n)=\lfloor n/2 \rfloor$,
$\tau(C_n)=\lceil n/2\rceil$, $\tau(K_n)=n-1$,
$\tau(K_{r,s})=\min(r,s)$.
12.54 HW (minimal vs. minimum vertex cover, 5 points)
Find a graph $G$ and a minimal vertex cover $T$
(meaning that no proper subset of $T$ is a vertex cover) such that
$|T| > 100\tau(G)$. Make your graph as small as possible.
12.56 DO Prove: for all graphs $G$ we have $\nu(G)\le \tau(G)$
where $\nu(G)$ is the matching number (maximum size of a matching).
This simple observation has an consequence that is important from an
algorithmic perspective.
12.58 Corollary (DO). If we have a matching $M$ and a cover $C$ in the
graph $G$ and $|M|=|C|$ then both of them are optimal ($M$ is a maximum
matching and $C$ is a minimum cover).
12.60 HW (5 points) Prove:
for all graphs, $\tau(G)\le 2\nu(G)$.
12.62 DO Prove that this bound is tight in the following sense:
For every $k\ge 0$ there exists a graph $G$ such that
$\nu(G)=k$ and $\tau(G)=2k$.
12.64 HW (6 points) Find a non-bipartite graph that satisfies
$\tau(G)=\nu(G)$. Make your graph as small as possible.
State the number of vertices and the number of edges of the graph,
state its matching number, and give a clear definition of the graph.
You do not need to prove minimality, or anything else, about the graph.
12.70 Theorem (Dénes König, 1931) If $G$ is a
bipartite graph then $\tau(G)=\nu(G)$.
12.72 METHOD OF AUGMENTING PATHS.
12.74 DO If $M$ is a matching and $P$ is an augmenting path
then the symmetric difference $M' = M \oplus E(P)$ is a matching
and $|M'|=|M|+1$. This observation suggests the following algorithm.
12.76 ALGORITHM
12.78 Theorem If $G$ is a bipartite graph then the algorithm
returns a maximum matching.
12.80 Lemma With the notation as above, assume there is no
augmenting path for the matching $M$.
Let $R$ denote the set of unmatched vertices in $U$.
Let $A$ denote the set of those vertices of $W$ that are accessible from
$R$ along alternating paths. Let $B$ denote the set of those vertices in
$U$ that are not accessible from $R$ along alternating paths. Then
$|A\cup B|=|M|$ and $A\cup B$ is a vertex cover.
12.82 DO Prove the Lemma.
12.84 DO Observe that the Lemma completes the proof of
Theorem 12.78 as well as the proof of König's Theorem.
12.86 HW (12 points) Execute line 03 of the algorithm in linear time:
given a bipartite graph $G$ and a matching $M$, find an augmenting
path or decide that none exists. Describe your algorithm in unambiguous
English. No analysis required. Simplicity counts. Hint: BFS.
12.88 DO If $G$ has no isolated vertices (vertices of degree 0)
then $m\ge n/2$. So in this case we can replace $O(n+m)$ by $O(m)$.
12.90 DO If $G$ is bipartite and has no isolated vertices then
a maximum matching can be found in $O(nm)$ time.
12.92 Theorem (Hopcroft-Karp, Karzanov, 1973)
Under the conditions of 12.90, a maximum matching
can be found in $O(m\sqrt{n})$.
12.94 The proof uses the same algorithm, with the additional requirement
that in each round, it selects a shortest augmenting path.
12.96 CH Prove the Hopcroft-Karp-Karzanov Theorem by showing that the
algorithm terminates in $O(\sqrt{n})$ rounds.
12.100 DEF We say that a sequence $a_n$ of real numbers
is polynomially bounded if there exists a polynomial
$f\in\rrr[x]$ such that for all sufficiently
large $n$ we have $|a_n| \le f(n)$.
12.102 DO Let $a_n$ be a sequence of real numbers.
Prove: $a_n$ is polynomially bounded if and only if
there exists $c$ such that $a_n=O(n^c)$.
12.104 DO Let $a_n\ge 1$ be a sequence of real numbers.
Prove: $a_n$ is polynomially bounded if and only if
$\ln a_n = O(\ln n)$. You may use the preceding exercises
without proof.
12.106 DO Prove: for every integer $k\ge 0$,
the sequence $b_n:=\binom{n}{k}$ is polynomially bounded.
12.108 HW (6 points)
Prove: the sequence $g_n:=\binom{n}{\lfloor \ln n\rfloor}$
is not polynomially bounded. You may use all preceding exercises
without proof. Elegance matters.
12.115 NOTATION $\exp(x) := \eee^x$.
12.117 DEF Let $a_n$ be a sequence of positive real numbers.
We say that $a_n$ grows exponentially if
$$(\exists \eps > 0)(a_n = \exp(\Omega(n^{\eps})))$$
12.118 EXAMPLE Let $b_n$ be a sequence of positive real numbers.
If for all sufficiently large $n$ we have
$b_n > \exp(\sqrt{n}/100)$ then $b_n$ grows exponentially.
12.119 DEF Let $a_n$ be a sequence of positive real numbers.
We say that $a_n$ grows simply exponentially if
$a_n = \exp(|\Theta(n)|)$ (so the exponent is between $c_1n$ and $c_2n$
for some positive constants $c_i$). In other words, there exist
constants $C_1, C_2 > 1$ such that for all sufficiently large $n$
we have $\Omega(C_1^n)\le a_n \le O(C_2^n)$.
12.120 DO If a sequence grows simply exponentially then it
grows exponentially.
12.121 DO Let $a_n$ be a sequence of positive real numbers.
Prove: $a_n$ grows exponentially if and only if the sequence
$(\ln \ln a_n)/(\ln n)$ is bounded away from zero, i.e.,
$\exists \delta > 0$ such that for all sufficiently large $n$
we have $(\ln \ln a_n)/(\ln n)\ge \delta$.
12.122 DEF The sequence of Fibonacci numbers is defined
as follows: $F_0=0$, $F_1=1$, and for $n\ge 2$,
$F_n=F_{n-1}+F_{n-2}$. So $F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$,
$F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, $F_8=21$, $F_9=34$,
$F_{10}=55$, $F_{11}=89$, $F_{12}=144$, etc.
12.123 DO Prove: the sequence $F_n$ (Fibonacci numbers) grows
simply exponentially. Your proof should be very simple, just a couple
of lines, using nothing but the definition of Fibonacci numbers.
12.125 DO Prove: the sequence $n!$ grows
faster than any simply exponential sequence, i.e., if
$a_n$ grows simply exponentially then $a_n = o(n!)$.
12.127 DO Let $h_n$ be a sequence of positive real numbers
such that $h_{n+1} \ge 1.001 h_n$ for all sufficiently large $n$.
Prove that $h_n$ grows at least simply exponentially.
12.129 HW (5+6 points)
(a) Find a sequence $d_n$ of positive real numbers that
grows exponentially but satisfies $d_n \sim d_{n+1}$. The description
of $d_n$ should be very simple, as should be the proof that $d_n$
satisfies the conditions. (b) Prove that such a sequence
cannot grow simply exponentially.
12.131 HW (5 points)
Let $a_n$ and $b_n$ be sequences of positive real numbers.
Suppose $a_n$ is polynomially bounded and $b_n$ grows
exponentially. Prove: $a_n = o(b_n)$
(exponential growth beats polynomial growth).
Do NOT use L'Hospital's rule. Use the fact that $\ln x = o(x)$
and make a change of variables.
12.140 Bit-length of input. We measure the complexity as
the number of bit operations in terms of the bitlength (number of bits)
of the input.
12.142 DO Let $x$ be a positive integer. Prove: the bitlength
of $x$ is $\lceil \log_2(x+1)\rceil$.
12.144 DO We try to decide whether the integer $x\ge 2$ is prime.
We proceed as follows.
Show that this algorithm takes simply exponential time.
12.146 HW (15 points)
On input $n$ we wish to compute the Fibonacci number $F_n$.
Prove that this takes simply exponential time. You need to prove both
a lower and an upper bound. The upper bound should be based on an algorithm.
The lower bound should be valid for all possible algorithms.
Estimate your constants $C_1$ and $C_2$ from DEF 12.119. The closer
they are, the better. (Warning: $n$ means a different thing in DEF 12.119
than in this problem. Recall that complexity is measured in terms of the
bit-length of the input.)
11.10 DEF Stack: FILO list (First-In-Last-Out).
Operations:
11.12 DEF balanced parantheses: a string of matching pairs of
parentheses without crossing pairs. This is a crossing pair
of parentheses: $\dots (1 \dots (2 \dots 1) \dots 2)\dots$,
which is illegal.
11.14 DO For any sequence of stack operations, the push/pop pairs
for the same key form a parenthesis structure.
11.16 DEF $\DFS(G,u)$ (rooted Depth-First Search):
In the code of BFS, replace the FIFO queue by a stack.
($G$ is a digraph, $u\in V(G)$ is the root.)
11.20 DFS, recursive description
Procedure $\DFS(G)$
(: overall DFS :)
INPUT: digraph $G=(V,E)$
INITIALIZATION
MAIN LOOP
Procedure $\DFS(G,u)$
(: rooted DFS :)
11 $\status(u)=\gray$
(: $u$ discovered :)
11.25 HW (7 points, due Feb 16)
For vertex $u$, let $d[u]$ denote its
discovery time and $f[u]$ its finish time. Augment the
pseudocode above to record discovery and finish times
(arrays $d$ and $f$).
11.27 DO Prove that the discovery and finish times form
a parenthesis structure.
11.30 HW (dependence of number of roots on numbering of vertices)
(12 points, due Feb 16)
Let $G=([n],E)$ be a digraph. For a permutation
$\pi$ of $[n]$, let $r(G,\pi)$ denote the number of roots created by
DFS if the input is $G$ with its vertices renumbered according to
the permutation $\pi$. Let $r_{\min}(G)=\min_{\pi} r(G)$ and
$r_{\max}(G)=\max_{\pi} r(G)$ where $\pi$ ranges over all the
$n!$ permutations of $[n]$. For every $n$, determine the quantity
$\Delta(n) = \max_G r_{\max}(G)-r_{\min}(G)$, where $G$ ranges over
all digraphs with $n$ vertices. Prove.
11.32 HW (12 points, due Feb 16)
Characterize the digraphs satisfying $r_{\max}(G)=1$.
Give a very simple necessary and sufficient condition. Prove.
11.34 HW (15 points, due Feb 16) Characterize the digraphs satisfying
$r_{\max}(G)=n$.
Give a very simple necessary and sufficient condition. Prove.
11.36 HW (12 points, due Feb 16) For every $n$, find a digraph $G$
that maximizes the difference $r_{\min}(G)-r_{\min}(G^-)$
among all digraphs with $n$ vertices,
where $G^-$ denotes the reverse of the digraph $G$. Prove that
your digraph achieves the maximum. The description of
your digraphs should be very simple.
11.38 Bonus (20 points, due Feb 16) Prove: for all digraphs,
$r_{\max}(G)=r_{\max}(G^-)$. Structure your proof (state a lemma).
Elegance counts.
11.45 DEF A descendant of vertex $u$ is a vertex discovered
by the routine $\DFS(G,u)$ in line 06 or line 15, including $u$ itself.
If $w$ is a decendant of $u$ then $u$ is an ancestor of $w$.
11.47 DO Prove: $w$ is a descendant of $u$ if and
only if $d[u]\le d[w] \le f[w] \le f[u]$.
11.55 DEF DFS creates four types of edges. An edge $(u,w)$
is a tree edge if $u=p(w)$. $(u,w)$ is a
forward edge if $w$ is a descendant of $u$ but $u\neq p(w)$.
$(u,w)$ is a back edge if $w$ is an ancestor of $u$.
$(u,w)$ is a cross edge if $w$ is neither a decendant
nor an ancestor of $u$.
11.57 DO Prove: If $(u,w)$ is a cross edge then
$f[w] < d[u]$.
11.59 HW (7 points) Find a smallest digraph that
has no cycle of length less than 3, and has all the four types
of edges. State the type of each edge in your digraph.
"Smallest" means it has the fewest possible edges.
You don't need to prove that it is smallest.
Describe your digraph in adjacency list format.
You are encouraged to attach a drawing (by hand is ok).
More to follow. Please check back later.
10.10 DEF Let $A=\{a_1, a_2,\dots,a_n\}$ be a set of $n$
distinct real numbers,
where $a_1 < a_2 < \dots < a_n$ be real numbers. We say
that the rank of $a_i$ in this set is $i$: $\rk(a_i)=i$.
10.12 DEF Let $B=[b_1, b_2,\dots,b_n]$ be a list of
$n$, not necessarily distinct, numbers. Let the sorted order
of these numbers be $c_1 \le c_2 \le\dots\le c_n$. We say that
$c_i$ is the $i$-th order statistic of $B$.
10.14 If all elements of $B$ are distinct then the $i$-th order
statistic of $B$ has rank $i$ among the set of elements of $B$.
10.16 If $n$ is odd then the $(n+1)/2$-nd order statistic of $B$
is called the median of $B$.
10.18 The MIN of $B$ is its 1st order statistic, and the MAX
of $B$ is its $n$-th order statistic.
10.20 DO (a) Find MIN using $n-1$ comparisons.
(b) Prove that you cannot find MIN in fewer than $n-1$
comparisons. In other words, if an algorithm claims to find
the MIN, it must make at least $n-1$ comparisons (not only in the
"worst case," but always).
(c) Same about MAX.
10.22 DO
Find both MIN and MAX, using fewer than $3n/2$ comparisons.
10.24 DEF The selection problem takes as input
a list of $n$ real numbers and a positive integer $r$ and
asks you to return the $r$-th order statistic.
10.26 DO Solve the selection problem using $\lesssim n\log_2 n$
comparisons.
10.28 Bonus (selection by rank lower bound, 15 points)
Prove: for any $r$ ($1\le r\le n$),
selection of the $r$-th order statistic among $n$ distinct items
requires at least $n-1$ comparisons.
10.30 THEOREM. Selection can be done using $O(n)$ comparisons
(Blum, Floyd, Pratt, Rivest, Tarjan 1973).
10.32 Overall strategy. We assume all elements of $B$
are distinct. We write $n=|B|$.
10.36 HW (7 points) If there exists a constant $c > 0$ and
an algorithm such that, given a list of $n \ge 3$ distinct real numbers,
the algorithm finds, using $O(n)$ comparisons, and element $x$
that satisfies $cn \le \rk(x) \le (1-c)n$,
then the selection problem can be solved
using $O(n)$ comparisons for any list of $n$ distinct integers
and target rank $r$ $(1\le r\le n)$.
10.38 Finding the pivot: a randomized algorithm.
10.39 DEF By "picking an element at random" from a non-empty
finite set $S$ we mean that every $x\in S$ has probability $1/|S|$
to be picked (uniform choice) (unless some other probability distribution
on $S$ is specified).
10.40 DO
Pick the pivot $x\in B$ at random. Ignoring rounding, the probability
that $(n+1)/4 \le x \le 3(n+1)/4$ is about $1/2$. Therefore,
in an expected two trials we shall find $x$ in this interval.
(It is like the expected number of coin flips to get "Heads".)
If $x$ is not in this interval, discard it. If it is, make $x$
the pivot. Your solution to 10.36 will show that this reduces
the number of elements to consider to $\lesssim 3n/4$ and leads
to the solution using expected $O(n)$ comparisons.
(Because of randomization, the number of comparisons will be
a random variable, and its expected value will be $O(n)$.)
10.45 Finding the pivot: a deterministic algorithm.
We ignore rounding. Divide up the $n$ items into $n/5$ buckets
of 5 items each. Find the median of each bucket. This costs
$\le 10$ comparisons per bucket (why?), total $\le 10\cdot n/5 =2n$.
10.47 HW (7 points)
Prove: $3n/10 \lesssim \rk(x)\lesssim 7n/10$.
10.49 DO
Ignoring small errors (replacing $\lesssim$ by $\le$), this leads to the
following recurrence on $T(n)$, the number of comparisons.
$$ T(n) \le 3n + T(n/5) + T(7n/10) $$
Why? We spent $\le 2n$ comparisons on finding the medians of the $n/5$
buckets. We spend $\le n-1$ comparisons on finding the rank of $x$ in $B$.
The cost of finding $x$ in $M$ is $T(n/5)$ (we apply our algorithm
recursively to the set $M$). Finally, by 10.47, both the "low set"
$L$ and the "high" set $H$ has size $\le 7n/10$, so we now need
to solve the selection problem on a set of size $\le 7n/10$,
which we do recursively, using the same algorithm.
10.51 HW (6+3+2 points)
(a) Let $T(n)\ge 0$ be a function satisfying $T(1)=0$ and
the inequality $T(n) \le T(\lfloor n/5\rfloor) + T(\lfloor 7n/10\rfloor)+3n$.
Prove: $T(n)=O(n)$. (b)
What is your best implied constant in the big-Oh
notation?
(c)
What is the smallest $n$ for which your bound is less than
$n\log_2 n$? (Do not ignore rounding.)
10.53 DO Make the argument above precise: do not ignore rounding,
do not ignore small errors. Try to make your argument still
reasonably elegant.
10.55 DO Find the median of 5 items using at most 7 comparisons.
10.57 DO How does 10.55 change the recurrence? How does it
change the implied constant?
10.59 Bonus (5+4 points)
(a) Show that in 10.49, the cost of finding the rank
of $x \in B$ is $\lesssim 2n/5$. (b) Taking this into account
and also 10.55, how do these two observations change the recurrence?
What is now the estimate on the implied constant? (Ignore rounding and
"small errors.")
10.70 DO Prove:
$\displaystyle{\lim_{x\to\infty} \frac{\ln x}{x} = 0}.$
Hint: L'Hospital's rule.
10.72 HW (5 points) Let $\epsilon > 0$ be a constant. Prove:
$\displaystyle{\lim_{x\to\infty} \frac{\ln x}{x^{\epsilon}} = 0}.$
Do NOT use L'Hospital's rule. Use simple algebra only: a substitution
of variables.
More to follow. Please check back later.
09.08 REVIEW the updated items 05.03-05.07 about link structures,
linked/doubly linked/cyclically linked lists, queues and stacks.
09.10 Recall that by graph we mean an undirected graph.
09.12 DEF A tree is a connected graph with no cycles.
09.14 DO Prove: a tree with $n\ge 1$ vertices has $n-1$ edges.
09.16 DO Prove: a graph is a tree if and only if between
each pair of vertices there is a unique path.
09.18 DEF Let $G=(V,E)$ be a graph. A subgraph is
a graph $H=(W,F)$ where $W\subseteq V$ and $F\subseteq E$.
09.20 DEF A spanning subgraph of $G=(V,E)$ is a
subgraph $H=(V,F)$ where $F\subseteq E$. So the spanning sungraph
has the same set of vertices as the graph.
09.22 DO If the graph $G$ has $m$ edges then it has
$2^m$ spanning subgraphs.
09.24 DEF A spanning tree is a spanning subgraph that
is a tree.
09.26 DO Prove: a graph $G$ has a spanning tree if and only if
$G$ is connected.
09.28 THEOREM (Cayley's formula) For $n\ge 1$, the complete
graph $K_n$ has $n^{n-2}$ spanning trees.
09.30 DO Verify Cayley's formula for $n = 5$. Hint.
Find all non-isomorphic trees with 5 vertices, and for each of these
trees, $T$, count the spanning trees of $K_n$ that are isomorphic to $T$.
09.35 Min-weight spanning tree problem. Let $G=(V,E,w)$ be
a weighted connected graph, where $w:E\to\rrr$ is the weight function.
Among all spanning trees of $G$, find one of minimum total weight.
(The weight of a subgraph is the sum of the weights of its edges.
Negative weights are permitted.)
09.37 HW (10 points) Solve the minimum-weight spanning tree problem
following Dijkstra's algorithm. Select any vertex as the root,
and perform Dijkstra's algorithm as described in the handout,
except for slightly modifying the RELAX routine.
The parent links will define the solution (the min-cost spanning tree).
Your answer should be a description of the
modified RELAX routine (lines 18-20 in the handout).
You do not need to prove that your algorithm is correct.
You also don't need to analyze the complexity; the analysis
should be identical with Dijkstra's.
09.50 DEF A rooted tree is a tree with a vertex declared
to be the root. If we wish to emphasize that a tree is not rooted,
we sometimes refer to it as a free tree.
09.52 DEF Let $T=(V,E,r)$ be a rooted tree, where $r\in V$
denotes the root. We usually refer to the vertices of a rooted tree
as nodes. If $v\in V$ is not the root then let $w$ be the first
node along the unique path from $v$ to $r$; we call $w$ the parent
of $v$ and denote it $w=p(v)$. We say that $v$ is a child of $p(v)$.
A leaf is a node with no children. The nodes along the
unique $v-r$ path (including $v$ and $r$) are the ancestors
of $v$. If $u$ is an ancestor of $v$ then $v$ is a descendant
of $u$. The set of nodes of a rooted tree is divided into layers.
The layer $L_0$ consists of $r$ alone. For $i\ge 1$, the nodes in
layer $L_i$ are the children of the nodes in layer $L_{i-1}$.
We have $v\in L_i$ if and only if the distance between $r$ and
$v$ is $i$. The depth of a node is its distance from $r$.
The height of a node is its distance from its farthest
descendent (which is necessarily a leaf). The height of
a rooted tree is the height of its root, which is the same
as the maximum depth of its nodes; therefore we also refer to
this quantity as the depth of the tree.
09.54 HW (7 points) Let $T$ be a rooted tree with $n$ nodes; let $L$
be the set of leaves of $T$. Assume none of the nodes in $T$
has exactly one child. Prove: $n < 2|L|$.
09.56 Bonus (13 points, due Feb 16)
(This exercise can be used to give an upper
bound on the complexity of a recursive algorithm.)
09.58 DEF A binary tree is a rooted tree where each node
has at most two children. In a binary tree, each child is designated
to be either a left child or a right child; there can only be one child
of each kind. We denote the left child of node $v$ by $lc(v)$
and the right child by $rc(v)$. We view a binary tree as
a link structure with the three types of links, $p$,
$lc$, and $rc$.
09.60 DO In a binary tree, $|L_i|\le 2^i$ for all $i\ge 0$
and the total number of nodes is $n \le 2^{d+1}-1$ where $d$
is the depth of the tree.
We say that layer $L_i$ is full if $|L_i|= 2^i$.
09.62 DEF A complete binary tree of depth $d$
is a binary tree of depth $d$ such that the
layers $L_0,\dots,L_{d-1}$ are full and layer $L_d$
is populated left to right. Let us number the nodes
by layers, moving left to right in each layer. So
$L_0=\{r\}=\{v_1\}$, $L_1=\{v_2,v_3\}$, $\dots$,
$L_i=\{v_{2^i}, v_{2^i+1},\dots, v_{2^{i+1}-1}\}$ for $i\le d-1$,
and $L_d = \{v_{2^d}, \dots, v_n\}$.
09.64 DO Let us consider a complete binary tree
with $n$ nodes. then for $j\ge 2$ we have $p(v_j)=v_{\lfloor j/2\rfloor}$;
for $j\le n/2$ we have $lc(v_j)=v_{2j}$ and for $j\le (n-1)/2$
we have $rc(v_j)=v_{2j+1}$.
09.66 Simulating the complete binary tree link structure by an array.
Take an array $A[1..n]$. For $2\le j\le n$ let $p(j)=\lfloor j/2\rfloor$.
For $1\le j\le n/2$ let $lc(j)=2j$. For $1\le j\le (n-1)/2$ let
$rc(j)=2j+1$. With these functions as links, we turned the array
into a complete binary tree.
09.68 DO (size vs. depth) Let $T$ be a complete binary tree with $n$
nodes. Let $d$ denote the depth of $T$.
Prove: $2^d \le n < 2^{d+1}$.
09.75 DEF A priority queue is a dynamic data structure
that serves the following instructions. Each data item is represented
as a pair $(id,\key)$ where $id$ is an identifier and $\key$ is a real number.
They always travel together, so we shall suppress the identifier.
09.79 DO Execute $\delete(v,\key)$ using the above commands.
09.81 HEAP implementation of the Priority Queue concept.
We assign the keys one-to-one to the nodes of a complete binary tree.
We say that this assignment satisfies the HEAP CONDITION if
09.83 DO In a heap, $\key(\root)=\min_v \key(v)$.
09.85 HW (bubbling up/down) (4+5 points)
09.87 HW (4+4 points) We are given a heap with $n$ heap-ordered
data. (a) Implement the EXTRACT-MIN
command using the INCREASE-KEY command once and $O(1)$ additional
link updates. Give the best upper bound on the number of comparisons
used in terms of the appropriate parameter of the tree.
Prove the bound; you do not need to prove it is best.
Do not use asymptotic notation.
09.89 DO Dijkstra's algorithm uses a Priority Queue.
Specifically, it uses the following Priority Queue operations:
INSERT $\le n$ times, EXTRACT-MIN $\le n$ times, DECREASE-KEY $\le m$
times.
09.91 DO If we use the HEAP implementation of Priority Queue
then the cost of Dijsktra's algorithm is $O(n+m)\log n$.
09.95 Fibonacci heap (Fredman-Tarjan, 1984). TO BE ADDED
09.110 HEAPSORT The Heapsort algorithm has two phases.
09.112 DO One way to implement HEAPIFY is by repeated insertions.
Give the best upper bound on the number of comparison used by this
method. This upper bound should be $\sim c n\log_2 n$. Find the
best constant $c$.
09.114 DO Prove that HEAPIFY can be performed using $O(n)$
comparisons. Find the implied constant.
09.116 HW (5 points) Prove:
$\displaystyle{\sum_{k=1}^{\infty}\frac{k}{2^k} = 2}$.
09.118 HW (7 points) Prove that Heapsort can be implemented
using $\lesssim cn \log_2 n$ comparisons for some constant $c$.
Find the best constant you can.
09.125 Bonus (HEAP preprocessing does not help, 20 points)
Let $\calA$ be an algorithm that takes
as input a heap-sorted list of data and returns the data in a sorted list.
$\calA$ is a comparison-based algorithm: the only thing it can do with
the data is pick two of them and compare them. Let $t(n)$ be the
number of comparisons performed by $\calA$ in the worst case, i.e.,
the maximum number of comparisons performed by $\calA$ on inputs
of size $n$ ($n$ items). Prove: $t(n)\gtrsim n \log_2 n$.
9.130 HW ($k$-way merge) (14 points, due Feb 23)
[UPDATE (Feb 16, 6:50pm) $O(i\log k)$ was replaced by $O(k+i\log k)$.
Because of this update, the problem is deferred by yet another week,
to Feb 23.]
More to follow. Please check back later.
08.10 REVIEW the "Dijkstra's Algorithm" handout.
08.12 STUDY the "Loop invariants" handout.
08.14 DO Solve all exercises in the "Loop invariants"
handout without looking up the solutions. (The solutions to the
more difficult exercises can also be found in the handout.) After
you solved them, review the solutions given, compare.
08.20 HW (4+4+4 points) Let $G=(V,E,s,w)$ be a rooted,
weighted digraph
with non-negative weights. We apply Dijkstra's algorithm to $G$.
Let $v\in V$. Consider the following three statements.
08.22 HW (5+5 points) (Previous exercise continued)
Consider the following two statements.
More to follow. Please check back later.
07.10 STUDY the "Greedy coloring" handout, referred to as GREDY-COL below.
(Click "Texts" on the banner.)
07.12 DEF The complete bipartite graph $K_{r,s}$
has $r+s$ vertices, split into a set $A$ of $r$ vertices and
a set $B$ of $s$ vertices; it has all the $rs$ edges between
these two sets.
07.14 DO GREEDY-COL, Problem (a) ("Greedy coloring is not so bad"):
07.16 HW (8 points) GREEDY-COL, Problem (b)
("Greedy coloring is terrible")
07.18 HW (6 points) GREEDY-COL, Problem (c) ("Greedy coloring
can be optimal")
07.20 Bonus (12 points, due Feb 9) GREEDY-COL, Problem (d)
("Greedy coloring in linear time").
Describe your algorithm in elegant pseudocode and
explain it in words. Prove that it works in linear time.
07.30 STUDY the "Dijkstra's Algorithm" handout (single-source
min-weight path problem for digraphs with nonnegative edge
weights). This includes understanding the PIORITY QUEUE
data structure concept. We shall implement this concept
in the next class.
07.32 HW (6 points) Give an example of a weighted digraph
with one negative edge and no negative cycles, where
Dijkstra's algorithm fails. Give the smallest example
(minimize the number of edges). You don't need to prove
minimality. Describe the result of each phase of the
algorithm (cost at each vertex, parent link). (One phase
is an execution of the while loop.)
07.34 REMARK about negative-weight edges.
07.36 Bonus (18 points, due Feb 9) Let $G=(V,E,w)$
be a weighted digraphs with $k$ negative-weight edges and no
negative cycles. Solve the single-source
min-weight path problem by running Dijkstra $2^k$ times;
each time, the input should be a subdigraph of $G$ (we may
delete edges and vertices). -- You will receive 8 points
if you solve the case $k=1$ only.
07.42 DO A DAG with a non-empty set of vertices has
a sink, i.e., a vertex of out-degree zero (no outgoing
edges).
07.45 DEF A topological sort of a digraph $G$
is an ordering of its vertices as $(v_1,\dots,v_n)$ such that
if $v_i\to v_j$ is an edge then $i < j$.
07.47 DO Prove that if a digraph $G$ has a topological sort
then $G$ is a DAG.
While the preceding exercise is very easy, the converse also holds.
07.49 DO A digraph $G$ has a topological sort
if and only if $G$ is a DAG.
07.51 DEF Let $G=(V,E)$ be a digraph and $A\subseteq V$. The
induced subdigraph on vertex set $A$ is the digraph
$(A,F)$ where $F=\{(u,v)\mid u,v\in A$ and $(u,v)\in E\}$.
We denote this digraph by $G[A]$.
07.53 DO A digraph with $n$ vertices has $2^n$ induced
subdigraphs.
07.55 DO Every induced subdigraph of a DAG is a DAG.
07.57 Proof of 07.49 (*) Let $G=(V,E)$ be a DAG.
We prove by induction on $n$ that $G$ has a topological sort.
07.59 HW (10 points)
Turn this proof into a linear-time algorithm.
The input of the algorithm is a digraph $G$. The output is
either a topological sort of $G$ or a certificate that $G$ is
not a DAG. The certificate must be a non-empty induced subdigraph
without a sink. (The presence of such an induced subdigraph certifies
that $G$ is not a DAG.)
07.65 Bonus (20 points, due Feb 9)
Let $G=([n],E, w)$ be a topologically sorted DAG (so if $i\to j$ is an
edge then $i < j$) with weighted edges; $w: E\to \rrr$ is the weight
function. Negative weights are permitted. (Note that there will be no
negative cycles because there are no cycles at all.)
06.10 DEF Given the digraph $G=(V,E)$ and $v_0\in V$, an edge $x\to y$
is accessible from $v_0$ if $x$ is accessible from $v_0$.
We denote the set of vertices accessible from $v_0$ by $V_0$ and
the set of edges accessible from $v_0$ by $E_0$ (if the
root $v_0$ is clear from the context).
06.15 Digraph traversal: given a digraph $G=(V,E)$ and a
root $v_0\in V$,
06.17 Status of vertices.
06.19 Status of edges and status change of vertices.
Parent links.
06.20 Assumption: A rooted traversal algorithm with root $v$
can be invoked only when the root is active ($\status(v)= \gray)$.
06.22 From rooted to full traversal. We descibe the
scheme to use a rooted traversal algorithm $\TRAV(G,v)$ to
obtain a full traversal algorithm $\TRAV(G)$.
01
for $u\in V$ set $\status(u):=\white$ and $p(u):=\NIL$
(: initialization :)
6.24 DO At the end of the execution of $\TRAV(G,v)$,
all vertices accessible from $v$ turn BLACK (will be finished).
6.26 DO (a) Let $v_0,\dots,v_k$ denote the sequence of vertices
that for which the if condition in the algorithm is satisfied
and therefore the execution of $\TRAV(G,v)$ is triggered. Then
$d_{v_0} < f_{v_0} < d_{v_1} < f_{v_1} < \dots < d_{v_k} < f_{v_k}$.
6.30 STUDY the Breadth-First Search handout
(click "Texts" on the banner).
REFRESH before clicking it; it was updated 1-27-2021.
You find the date in the footnote on the first page.
6.40 RECALL DEF: A digraph is strongly connected if for every
pair $(u,w)$ of vertices there exists a $u\to\to w$ path.
6.42 HW (8 points)
Given a digraph $G=(V,E)$ in adjacency list representation,
decide in linear time whether $G$ is strongly connected. Do NOT use DFS.
Use only BFS and algorithms discussed earlier. With reference to these
algorithms, your algorithm should take just a few lines. Briefly
reason correctness (what property of accessibility is used in your
argument?) and the complexity bound.
6.50 Study the "Car-race" handout.
05.02 Notation. For $n\ge 0$ we write $[n]=\{1,\dots,n\}$. Note
in particular that $[0]=\emptyset$.
05.03 Representation of lists. We use the following two representations
of a list $[a_1,\dots,a_n]$ of items: array and linked list.
05.05 A queue or "FIFO list" (first-in first-out)
is a data structure $Q$ that supports two types of requests:
$\enqueue(Q,v,\key)$
and $\dequeue(Q)$. The effect of the enqueue instruction
is that it adds the item
$(v,\key)$ at the end of the list; the new item becomes the new tail.
The effect of the dequeue instruction
is that it returns the head of the list and removes
it from the list, updating the head, or returns "empty" if the list was
empty.
05.07 A stack or "FILO list" (first-in last-out)
is a data structure $Q$ that supports two types of requests:
$\push(Q,v,\key)$ and $\pop(Q)$. Thepop operation is the same
as dequeue: it returns the head and removes it from the list.
Thepush operation is almost the same as enqueue, the important
difference being that the new item is added in front and becomes
the new head.
05.10 Representations of digraphs. We represent the set
of vertices as an array, $[v_1,\dots,v_n]$.
05.20 HW (conversion between representations, 6+6 points)
Let $G=(V,E)$ be a digraph ($E\subseteq V\times V$)
where $V=[n]=\{1,\dots,n\}$.
05.25 (reverse digraph, worked example)
Given a digraph $G=(V,E)$ in adjacency-list representation,
construct an adjacency-list representation of the
reverse digraph $G^-=(V,E^-)$ (each edge reversed)
in linear time. Describe your algorithm in a very simple,
elegant pseudocode. Assume $V=[n]$.
INPUT: $\adj$
(: array of linked lists representing $G$ :)
for $j=1$ to $n$
The reason this algorithm works in linear time is that
for every item in the input (adjacency lists) it performs a
constant number of operations (read/copy numbers $i,j\in [n]$,
do random access using such a number as an address, advance
on a link in a linked list).
05.30 HW (monotone adjacency-lists, 6 points)
We say that an adjacency list is monotone if for each vertex,
its neighbors are listed in increasing order. Given a digraph
$G=(V,E)$ in adjacency-list representation, convert this to
a monotone adjcency-list representation in linear time.
Your algorithm should be very simple, just a couple of lines,
with reference to previously seen algorithms.
Explain in words what your algorithm is doing.
05.32 HW (undirectedness test, 6 points, due Feb 2)
We say that a digraph $G$ is undirected if $G=G^-$.
Given a digraph in adjacency-list representation, decide
in linear time whether it is undirected. Write a very simple
pseudocode, with reference to previously seen algorithms.
Explain in words what your algorithm is doing.
04.03 STUDY The Knapsack problem ("KNAP") handout
04.10 HW (8 points) Handout:
All-ones square.
Note: this is a dynamic programming problem.
Write your solution in elegant pseudocode.
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.
04.12 Bonus (Integer-Valued Knapsack) (14 points) 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.)
04.18 DO Let $a_1,\dots,a_n$ be a list of integers $a_i\in [m]$,
given as a linked list. Remove all repeated items from the list
in time $O(n+m)$. Operations with numbers in $[m]$ have unit cost
(reading and copying such a number).
04.20 REVIEW Radix sort: sorting a list of $n$ words of length $k$
over an alphabet $\Sigma$ of size $s$. (The alphabet is an
ordered set.) The list is represented
as an $n\times k$ array. Example:
INPUT OUTPUT
BBB ACC
Algorithm (high-level description)
INPUT: $n\times k$ array $M$
for $j=k$ downto $1$
04.22 DO Prove the correctness of the algorithm.
04.24 Complexity of Radix-sort, implementation in linear time.
Example. OUTPUTj represents the result of sorting by the $j$-th column.
The items in parentheses are not printed by the algorithm.
INPUT OUTPUT3 OUTPUT2 OUTPUT1
1 BBB 4 (BBA) 2 (BAC) 3 ACC
04.26 HW (8 points, due Tue, Feb 2) Write a pseudocode for
Radix sort that includes the implementation of Counting sort as discussed.
The words are of equal length.
04.30 Lexicographic order of words of variable length.
AB
Bonus 4.32 (18 points, due Tue, Feb 2)
Given an array of words over the alphabet $\Sigma$,
sort these words lexicographically.
1 ABB
Here, the first column is an array.
03.03 STUDY (due Thu, Jan 21, noon): ASY (all sections).
03.10 Information Theory lower bound. A set $S$ of $N$ objects
has been aggreed between Alice and Bob. Alice (mentally) selects one
of the objects. Bob asks YES/NO questions. The goal is for Bob
to find out which object Alice selected. The cost is the number of
queries (questions asked) in the worst case, i.e., $m=\max_{x\in S} q(x)$
where $q(x)$ is the number of questions Bob asks if $x$ is the selected
object. (So this is "worst-case complexity").
03.12 Theorem. $m\ge \log_2 N$.
03.14 DO: State and prove the Information Theory lower bound
for ternary queries (each question has 3 possible answers).
03.16 The DECISION TREE model. We can model the process by
a rooted tree. Each node $z$ corresponds to a subset $T(z)\subseteq S$.
If $r$ denotes the root then $T(r)=S$. The leaves correspond to singletons
(sets of the form $\{x\}$ with just a single element). Each element of $S$
appears at at least one leaf. If the children of node $z$ are
$w_1,\dots,w_k$ then $\{T(w_1),\dots,T(w_k)\}$ form a partition of $T(z)$,
i.e., $T(z)$ is the disjoint union of the $T(w_i)$. The complexity
of the process is the height of the tree (length of longest path from
root to leaf).
03.17 Note. The model described above
is a special case of the Decision Tree model. In the
general Decision Tree model, the goal is not to determine $x\in S$
but to find some attribute of $x$ (evaluate a function $f(x)$).
03.20 Comparison-based sorting. The input is a list of real
numbers, $x_1,\dots x_n$. We have no access to this input; the
only way we can get information about it is by asking comparison
questions, i.e., questions of the form $x_i \stackrel{?}{\le} x_j$.
We wish to sort the input, i.e., find an ordering $(i_1,\dots,i_n)$
of the set $\{1,\dots,n\}$ such that
$x_{i_1} \le x_{i_2} \le \dots \le x_{i_n}$. The cost is the
number of comparisons made. Again, we are interested in the
worst-case complexity, i.e., the maximum number of comparisons
required by any input.
3.22 Theorem. Comparison-based sorting of $n$ data requires
$\ge \log_2(n!)$ queries.
3.25 HW (6 points, due Jan 26). Prove for all $n\ge 1$ that
$n! > (n/\eee)^n$.
3.26 Corollary. Comparison-based sorting of $n$ data requires
more than $n(\log_2 n - \log_2 \eee) > n(\log 2 n - 1.4427)$ queries.
3.28 HW (5+3 points, due Jan 26).
Prove $\log_2(n!) \sim n \log_2 n$.
3.30 HW (MERGE, 5 points, due Jan 26).
Let $A[1,\dots,k]$ and $B[1,\dots,\ell]$ be sorted lists
of data (real numbers): $A[1]\le A[2]\le \dots \le A[k]$ and
$B[1]\le B[2]\le \dots \le B[\ell]$, given as linked lists or arrays.
Write an elegant pseudocode to compute the merged list $C[1,\dots,k+\ell]$
using $\le (k+\ell-1)$ comparisons of data.
3.34 MERGE-SORT. We describe a recursive algorithm to sort
an array $A[1,\dots,n]$ of reals.
3.36 DO Reason that the algorithm is correct (returns
the sorted list).
3.38 DO Let $C(n)$ denote the number of comparisons
use by MERGE-SORT. Observe that
$C(n) \le C(\lfloor n/2\rfloor)+C(\lceil n/2\rceil)+(n-1).$
3.40 DO Infer that $C(n)\le n\log_2 n.$
3.45 COUNTING SORT
for $j=1$ to $m$
3.47 HW (4 points, due Jan 26).
Write an elegant pseudocode for the following computation.
02.03 STUDY the handout KARATSUBA ("Divide and Conquer: the Karatsuba
algorithm"). (Click "Handouts" on the banner.)
02.05 STUDY the handout "REV-INEQ" ("Evaluation of recurrent
inequalities: The method of reverse inequalities").
02.10 HW (3+4 points)
Prove REV-INEQ Theorem 3 by solving REV-INEQ Exercises 4 and 5.
02.12 Bonus (12 points) REV-INEQ Exercise 8.
02.18 (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.") 02.20 (6+9 points) (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.
01.01 If you have not done so yet, please
answer the questionnaire on
the course home page (by email). Deadline: Thursday, Jan 14, noon.
01.03 STUDY (due Thu, Jan 14, noon):
MR20 Section 1 (items 1.10--1.116: quantifier notation, divisibility,
congruence modulo $m$) and Section 4 (items 4.08--4.80:
greatest common divisor). DO: Solve all exercises in
these sections by Sun, Jan 17.
01.05 STUDY (due Thu, Jan 14, noon):
ASY, Sections 1--3 and DM, Sections 2.1, 2.3, 2.4
(asymptotic notation). Study also ASY Ex. 6.15.
This subject will be discussed
in Thursday's discussion sessions.
DO:
Solve all exercises in these sections by Sun, Jan 17.
01.06 STUDY (due Sun, Jan 17):
"Binary search" handout. (Click "Handouts" on the banner.)
01.07 STUDY (due Sun, Jan 17):
"Divide and Conquer: the Karatsuba integer multiplication algorithm" handout
01.09 (Due: continuous)
STUDY each HANDOUT related to class material.
(Click "Handouts" on the banner.)
In the HANDOUTS, most algorithms are described in pseudocode.
STUDY from these samples and also from the homework LaTeX template
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.
01.12 HW (9+5 points) (a) Let $n$ be an integer.
Let $a=8n-3$ and $b=21n+5$. Prove: $\gcd(a,b)\in\{1, 103\}$.
Give a short proof. Elegance counts.
(b) Find the smallest positive value of $n$ such that
$\gcd(a,b)=103$. Show your work -- how did you find $n$.
01.15 HW (7 points) (asymptotic equality vs. little-oh notation)
Find two sequences $a_n$ and $b_n$ of positive real numbers
such that $a_n \sim b_n$ but $a_n^n = o(b_n^n)$. Prove that
your answer is correct. The proof should be short
and elegant. Elegance counts.
01.17 HW (5+5+5+5B points) (a) Let $a_0, a_1,\dots$ be
an infinite
sequence of real numbers $a_i > 1$. Prove: if $a_{n+1}=O(a_n)$ then
$\ln a_n = O(n)$. (b) Find an infinite sequence of real numbers
$a_i > 1$ such that $\ln a_n = O(n)$ but the $a_{n+1}=O(a_n)$ relation
does not hold. (c) Let $a_n = \eee^{\sqrt{n}}$.
Prove: $a_{n+1}\sim a_n$. (d) (Bonus)
Let $a_0, a_1,\dots$ be an infinite
sequence of real numbers $a_i > 1$. Prove: if $a_{n+1}\sim a_n$ then
$\ln a_n = o(n)$ (little-oh).
01.19 HW (6+6 points) ASY 3.6 (a) (b)
(taking the log of an asymptotic equality?)
01.21 Bonus (16 points) ASY 6.21 (solvig an asymptotic inequality).
You may use all exercises before 6.21 in ASY without proof,
but state what you are using.
01.25 DO (communication complexity) Review the model
of "communication complexity" from you class notes.
01.27 REVIEW (communication complexity of equality)
Alice and Bob each receive an $n$-bit $(0,1)$-string
(string of zeros and ones), $X$ and $Y$, respectively.
They wish to decide whether $X=Y$.
Alice and Bob each have unlimited computational power
and are also permitted to use private random bits (flip their own coins).
The cost of their procedure is the maximum number of bits they
communicate, where the maximum is taken over all possible inputs
$(X,Y)$ and all possible outcomes of the coin flips.
(This measure is called worst-case analysis.)
The correctness of their procedure
is measured by the maximum probability that they return an
erroneous decision, where the maximum is taken over all
possible inputs $(X,Y)$, and the probability refers to
the dependence of the outcome on the random bits used.
They agree on a number $k$ that is much smaller than $n$; the right
value of $k$ will come from our analysis. Alice and Bob view
their input strings as $n$-bit numbers in binary. For an integer $X$
and a positive intereg $p$, the notation
$(X \bmod p)$ denotes the smallest nonnegative remainder
of dividing $X$ by $p$.
(Example: $(83 \bmod{17})=15$ because $83=4\cdot 17+15$.)
01.29 Notation For an integer $m$, let $\nu(m)$
denote the number of distinct prime divisors of $m$.
01.31 HW (3 points) Find the smallest positive integer $m$
such that $\nu(m)=5$. No proof required.
01.33 HW (5 points) Let $m$ be a positive integer.
Prove: $\nu(m) \le \log_2 m$.
01.35 CH Use the Prime Number Theorem (but no other
hard results) to prove that
$$\nu(m) \lesssim \frac{\ln m}{\ln\ln m}\,.$$
(See ASY for the notation "$\lesssim$".)
01.37 DO Let $P(X,Y)$ denote the probability that Bob's
declaration is in error given the input $(X,Y)$.
01.39 DO Using 01.33, observe that if $X\neq Y$ then $\nu(X-Y)\le n$.
01.41 DO (a) Infer from the Prime Number Theorem (see ASY) that
$\displaystyle{\pi(2^k) \sim \frac{2^k}{k\ln 2}}\,.$
01.43 DO It should now be immediate that
$$P(X,Y) < \frac{5}{7}\cdot\frac{n\cdot k}{2^k}\,$$
for all sufficently large values of $k$.
01.45 Bonus (5 points) Let $k = \log_2 n + \log_2\log_2 n +C$ where
$C$ is a positive constant. Use Ex. 01.43 and ASY 6.15 to prove that
$P(X,Y) < 2^{-C}$ for all sufficiently large values of $k$ when $n\ge k$.
01.47 Bonus (5 points)
Use Ex. 01.35 and ASY 6.15 to prove that
$$ P(X,Y) \lesssim \frac{n}{\log_2 n}\cdot\frac{k}{2^k}$$
as $k\to\infty$ and $n\ge k$.
01.49 DO
Let $k = \log_2 n + C$ where $C$ is a positive constant.
Use the preceding exercise to prove
$P(X,Y) \lesssim 2^{-C}$.
01.55 HW (18 points)
As before, Alice is given an $n$-bit integer $X$ and Bob is
given an $n$-bit integer $Y$ (initial zeros are permitted).
Having executed the Rabin protocol, Alice and Bob
have shared knowledge of a $k$-bit prime number $p$ (where
the specific value of $k$ is irrelevant for this problem) such that
$X \not\equiv Y\pmod p$. This proves that $X\neq Y$, but now
the space aliens also demand that Alice and Bob determine
a position $i$ ($1\le i\le n$) such that $X[i]\neq Y[i]$
(where $X[i]$ denotes the $i$-th bit of $X$, and similarly
for $Y$). Prove that Alice and Bob can accomplish this task by
an additional $\le (k+1)(1+\log_2 n)$ bits of
deterministic communication (back and forth)
between Alice and Bob. (No coins flipped.)
Give a clear description of the protocol, and a clean analysis.
You may refer to a relevant handout.
01.57 Bonus (8 points)
Prove: there exists a constant $C$ such that if $k\ge C$ then
Alice and Bob need fewer than $(k+1)((\log_2 n) - 100)$ bits
of communication in the preceding problem. Estimate $C$;
make it as small as you can.
Class #26, Fri, Mar 12
Clearly state your answer (True of False).
If true, prove. If false, find the smallest counterexample.
If you are satisfied with your previous solution,
you may submit the relevant part of the same solution.
(You are not guaranteed to receive the same number of points.)
Clarity, accuracy are paramount.
Class #25, Wed, Mar 10
Therefore no polynomial-time algorithm can solve the integer
Knapsack problem, unless $\calP=\NP$.
A fully polynomial-time approximation scheme (PTAS)
finds such an approximation in time, polynomial in
$n$ (the bitlength of the input) and $1/\epsilon$.
Examples: a time bound of $2^{1/\eps}n^2$ or $n^{1/\eps}$
would give a PTAS, but not a FPTAS. A time bound of
$n^2/\eps^3$ gives a FPTAS.
For 7 points credit, prove the conclusion without the $O(n^2)$ term
in the assumption.
(a) If the
maximum degree of the graph is $\le 2$ then find a maximum independent
set in linear time. Describe your algorithm in simple and elegant pseudocode.
Briefly justify the time bound.
(b) Find a maximum independent set (in any graph) in time $O(c^n)$
where $c\approx 1.38$ is defined in the preceding exercise.
Describe your algorithm in simple pseudocode. Define your
variables. Analyze the algorithm.
The main difficulty with this approach is that it may reach a
local maximum, meaning that no string $y$ in the vicinity
of $y_0$ improves the value of the objective function, yet the
value $f(x,y)$ may be far form the actual optimum.
Let us try the local search approach for this problem.
(a) Let us first consider 1-local maxima. (We are allowed to flip
at most one bit.)
(a1) HW (6 points)
Find a non-empty instance of MAX3SAT (the formula has $m\ge 1$
clauses) and a 1-local maximum that satisfies only a $3/4$ fraction
of the clauses. Find the smallest instance (minimize $m$).
(You do not need to prove it is smallest.)
(a2) Bonus (20 points)
Prove that the factor $3/4$ is optimal: every 1-local maximum of
any MAX3SAT instance satisfies at least a $3/4$ fraction of the
clauses.
(b) Let us now consider 2-local maxima.
(b1) HW (4 points)
Find a non-empty instance of MAX3SAT (the formula has $m\ge 1$
clauses) and a 2-local maximum that satisfies only a $6/7$ fraction
of the clauses. Find the smallest instance (minimize $m$).
(You do not need to prove it is smallest.)
(b2) CH
Is the $6/7$ factor optimal? (I don't know the answer.)
(c) CH True or false: a 3-local maximum satisfies
at least a $7/8$ fraction of the clauses. (I don't know the answer.)
Class #24, Mon, Mar 8
Class #23, Fri, Mar 5
Use the Duality Theorem for the proof. Note, however, that historically,
the Duality Theorem (Albert Tucker, 1948) was derived from Farkas's
Lemma (Gyula [Julius] Farkas, 1902).
(A) INPUT: positive integers $k,n$,
integer matrices $A\in\rrr^{k\times n}$, $b\in \rrr^k$.
QUESTION: is the system $Ax\le b$ feasible,
i.e., does there exist $x\in \rrr^n$ such that $Ax\le b$?
(B) INPUT: same as for (A)
QUESTION: is the system $Ax\le b, x\ge 0$ feasible,
i.e., does there exist $x\in \rrr^n$ such that $x\ge 0$ and $Ax\le b$?
QUESTION: is the system $Cy\le d, y\ge 0$ feasible,
i.e., does there exist $y\in \rrr^m$ such that $y\ge 0$ and $Cy\le d$?
Class #22, Wed, Mar 3
The construction and the proof must be elegant.
Inductive constructions will not be accepted.
(b) Construct the $k\times s$ incidence matrix of these $k$
events in time $O(k^2\log k)$. Here we count bit operations,
so we are not using the unit cost model.
UPDATE (03-04, 10pm): This problem has been deferred to Mar 19.
UPDATE (03-07, 1:15pm): Last sentence (clarification of
model) added.
Solutions that do not essentially use 3-wise independence
will not be accepted. We are using the "unit cost" model:
$O(\log(n+m))$-bit integers
can be used as addresses into arrays at unit cost
and arithmetic on such integers can be performed at unit cost.
UPDATE (03-07, 1:25pm): Last sentence (clarification of
model) added.
UPDATE (03-08, 03:05pm): Upper bound reduced to $O(mn)$.
(Yuo will receive full credit for $O(n(n+m))$.)
Let $(B_1,\dots,B_k)$ be a partition of $\Omega$
into blocks $B_i$ of positive probability and let
$X$ be a random variable. Then
$$ E(X) = \sum_{i=1}^k E(X\mid B_i) P(B_i)\,.$$
Given a list of disjunctive$^*$ clauses, we shall assign
Boolean values to the variables, one at a time, so that
the expected number of satisfied clauses (under random
assignment to the remaining variables) never decreases.
In the end, when all variables will have assigned values,
the number of satisfied clauses will be at least the
originally expected number.
OUTPUT: an assignment of Boolean values to the variables
such that at least as many of the clauses are satified as
the expected number of satisfied clauses under a random assignment.
$R$ will be the list of subscripts of the yet unassigned variables.
$u \in \{0,1\}^{[n]\setminus R}$ will be the string of assignments
made so far.
01 $R=[n]$, $u=\Lambda$ (the empty string)
02 for $j=1$ to $m$ do $D_j:=C_j$
Main loop
03 while $R\neq\emptyset$
04 let $X$ denote the number of satisfied
clauses $D_j$ under a random assignment of the unassigned variables
05 pick $\ell\in R$
06 for $\epsilon\in\{0,1\}$
let $X^{\epsilon}$ denote the number of satisfied clauses
$D_j^{\ell,\epsilon}$ $(j=1,\dots,m)$
under a random assignment of the unassigned variables
($x_{\ell}$ now excluded)
07 end(for)
08 (: Note that $E(X)= (1/2)(E(X^0)+E(X^1))$ :)
09 if $E(X^0)\ge E(X^1)$ then
$\delta:=0$ else $\delta:=1$
(: Note: $E(X) \le E(X^{\delta})$ :)
10
for $j=1$ to $m$ do $D_j:=D_j^{\ell,\delta}$
(: we restrict $D_j$ by assigning $x_{\ell}:=\delta$ :)
11 end(for)
12 add $\ell\mapsto \delta$ to $u$ and
delete $\ell$ from $R$
13 end(while)
14 return $u$
UPDATE (3-13 2:45am): last sentence added.
UPDATE (3-15 2;15pm): Problem reclassified as Bonus (previously HW),
to make it consistent with its listing on Gradescope.
Class #21, Mon, Mar 1
Solution. First we observe that $X$ is a random variable:
for $a\in \Omega$ we have $X(a)=|\{i\mid a\in A_i\}|$. (Verify!)
Next we observe that $X=\sum_{i=1}^k Y_i$ where $Y_i$ is the
indicator of the event $A_i$. So $E(Y_i)=P(A_i)$.
Finally, by the linearity of expectation,
$E(X)=\sum_{i=1}^k E(Y_i)=\sum_{i=1}^k P(A_i)$.
Note: Every $x\in [n]$ belongs to exactly one cycle.
Class #20, Fri, Feb 26
All exercises are due Tue, Mar 9, except where stated otherwise.
Class #19, Wed, Feb 24
All exercises are due Tue, Mar 2, except where stated otherwise.
UPDATE (03-04, 10pm): &bsp; This problem has been deferred to Mar 19.
Class #18, Mon, Feb 22
All exercises are due Tue, Mar 2, except where stated otherwise.
UPDATE (3-1 9:30pm): As usual, you can use exercises that precede this one.
Class #17, Fri, Feb 19
All exercises are due Tue, Mar 2, except where stated otherwise.
UPDATE (2-26 2:40am) The condition $\gcd(x,a)=1$ added.
UPDATE (2-26 2:40) Definition of "simple witness" corrected.
Note that the two outputs overlap: either answer is correct
if $x$ is a Carmichael number.
Let $1\le a\le x-1$. We say that the integer $a$ is a Miller witness
(after its inventor, Gary L. Miller) if the following procedure
returns "YES".
Procedure UPDATED 02-26 9:00pm
02 Else $y:=x-1$
03
while $y$ even and $a^y\equiv 1 \pmod x$
04
$y :=y/2$
05
if $a^y \not\equiv\pm 1 \pmod x$
then return YES
06
end(while)
07
return NO
the relation signs are as follows:
line 01: "not congruent modulo $x$",
line 02: "let it be equal", line 03: "congruent modulo $x$",
line 04: "let it be equal", line 05: "not congruent to
plus/minus 1 modulo $x$".)
WARNING: Miller test UPDATED 02-26 9:00pm
UPDATE (03-08 3pm) "relatively prime" conclusion added.
UPDATE (03-08 3pm) "relatively prime" condition added.
Both the Miller-Rabin test and the Solovay-Strassen test
require $O(nt)$ arithmetic operations on $n$-bit integers
(where $n$ is the bit-length of the input number).
After some improvements, currently the algorithm uses $O(n^4)$
arithmetic operations on $n$-bit integers
(where $n$ is the bit-length of the input number).
This complexity is expected to go further down.
Example: $(41 \bmod 13)=2$, $(-41 \bmod 13)=11$.
Class #16, Wed, Feb 17
All exercises are due Tue, Feb 23, except where stated otherwise.
Here $B(\ul\alpha)$ denotes the matrix obtained by
substituting the scalar $\alpha_i$ for the variable $x_i$.
Note that $\det C$ is a polynomial in $m$ variables.
Notation: $G=(V,E)$ is the digraph to which we are applying DFS.
For vertex $v\in V$, we write $d_v$
to denote the discovery time and $f_v$ the finish time of $v$.
(a) $d_u\le f_u < d_v \le f_v$ and neither $u$
nor $v$ is a descendant of the other
(b) $d_u < d_v \le f_v < f_u$ and $v$ is a
descendant of $u$.
This is not an algorithmic problem; give an explicit expression
for the entries of this matrix in terms of a familiar sequence.
Prove your answer. ($n$ is a nonnegative integer.)
UPDATE (2-20, 10:55pm): parenthetical clarification added.
UPDATE (2-23 1pm): We are in the "unit cost" model: manipulating
letters of the alphabet (reading, copying a letter, comparing
two letters whether they are equal) counts as one step,
as does manipulation of non-negative integers not greater than
$k+m$ (reading, copying, arithmetic, addressing into an array).
One we assign Boolean values to the children of a gate, the
gate itself computes a Boolean value in the natural manner,
taking possible negations into account. If we assign
Boolean values to each input variable, we inductively
evaluate all gates: once all children of a gate have
been evaluated, the gate itself gets a value.
This way a Boolean circuit evaluates a Boolean function.
We shall see that every Boolean function is represented by a
Boolean circuit.
Answer (verify!):
$x\oplus y = (x \vee y)\wedge(\xbar \vee \ybar) =
(x \wedge \ybar)\vee(\xbar \wedge y)$.
State the best constant you can achieve in the exponent.
(For 8 points credit, prove this bound in depth 4.)
UPDATE (2-28 12:50pm) Previously the bound on the size was
errorneously stated as $O(n\cdot 2^{\sqrt{n}})$. This bound
is valid for depth 4 but not known to be valid for depth 3.
Class #15, Mon, Feb 15
All exercises are due Tue, Feb 23, except where stated otherwise.
UPDATE: Part (b) erroneously gave PROB 7.4.18. Corrected 2-20 0:45am.
(7.4.18 correctly appears in the next problem.)
Prove: If $f$ is not the identically zero polynomial then
$P(f(\ul\alpha)=0) \le d/N$.
Class #14, Fri, Feb 12
All exercises are due Tue, Feb 16, except where stated otherwise.
UPDATE (Feb 16 6:30pm) This problem is deferred to Feb 23
because on Gradescope it appeared as "HW" rather than "Bonus".
UPDATE (Feb 22, 1:30am): Originally, this problem was listed as "HW".
Estimate the number of oracle queries made;
make this number as small as you can.
(UPDATED Fri Feb 19 8am)
Class #13, Wed, Feb 10
All exercises are due Tue, Feb 16, except where stated otherwise.
Class #12, Mon, Feb 8
All exercises are due Tue, Feb 16, except where stated otherwise.
UPDATE (Feb 16 6:15pm): word "shortest" added. The word "shortest"
appeared in the statement posted on Gradescope. However, because of
this discrepancy, the problem is deferred to next week.
(The condition that $V=[n]$ was added 2-15 3am.
Compare also with DEF 5.20.)
UPDATE (Feb 16 6:15pm): This problem is deferred to Feb 23
because on Gradescope it appeared as "HW" rather than "Bonus".
Let $G=(V,E)$ be a bipartite graph,
where $V= U \cup W$ is the partition of $V$ into two parts (corresponding
to the two vertex- colors). Let $M$ be a matching in $G$.
Let us color its edges red, all other edges blue. An alternating
path is a path whose edges alternate colors. An augmenting
path is an alternating path that starts at an unmatched vertex
in $U$ and ends at an unmatched vertex in $W$.
INPUT: bipartite graph $G$
Output: matching $M$
01 $M=\emptyset$
02
while there exists an augmenting path to $M$
03
find an augmenting path $P$
04
$M := M \oplus E(P)$
05 end(while)
06 return $M$
This notation is recommended when $x$ is a tall expression
involving subscripts, exponents, fractions, etc.
$d:=1$
while $d^2\le x$
if $d \mid x$ then return "composite", exit
end(while)
return "prime"
Class #11, Fri, Feb 5
All exercises are due Tue, Feb 9, except where stated otherwise.
So what is permitted is $\dots (1 \dots 1) \dots (2 \dots 2)\dots$
(disjoint pair) and $\dots (1 \dots (2 \dots 2) \dots 1)\dots$
(nested pair). A parenthesis structure is a string on
balanced parentheses.
OUTPUT: list $R$ (list of roots), $p$ array of parent links, $\status$ array
01 $R:=$ empty list
02 for $v\in V$ do
$\status(v):=\white$, $p(v)=\NIL$
03 for $v\in V$
04
if $\status(v):=\white$
05
add $v$ to $R$
(: $v$ becomes new root :)
06
$\DFS(G,v)$
(: calls rooted DFS routine :)
07 end(for)
08 return $R$, $p$
12 for $w\in \adj(u)$
13
if $\status(w)=\white$
14
$u := p(w)$
15
$\DFS(G,w)$
(: recursive call :)
16
end(for)
17
$\status(u)=\black$
Class #10, Wed, Feb 3
All exercises are due Tue, Feb 9, except where stated otherwise.
Example: let $A=\{16,12,34,3,17\}$. Then $\rk(17)=4$ and $\rk(3)=1$.
Example: let $B=[5,7,5,5,8,7]$. Then the 4th and 5th order statistics
are equal to 7, and the 1st, 2nd, and 3rd are equal to 5.
Note. This is a gem. How could looking for MIN help find
MAX? Yet it does. The algorithm is not difficult
to find, and once you found it, the idea is rewarding.
DO NOT LOOK THIS UP, figure it out yourself.
You are denying yourself the opportunity of a memorable
intellectual experience if you just look it up.
Our goal will be to reduce this trivial upper bound to $O(n)$.
Hint. Even if an untrusted party reveals
you the $r$-th order statistic, just to check if this answer
is correct requires $n-1$ comparisons.
We prove this result in a series of exercises below.
The solution is a rather surprising application of
the "Divide & Conquer" technique.
Pick an element $x\in B$, which we call the pivot,
compare it to all other elements to determine its rank,
$\rk(x)=t$. This set of comparisons will also reveal
the set $L$ of $t-1$ elements of rank $\le t-1$ ("L" for "low")
the set $H$ of $n-t$ elements of rank $\ge t+1$ ("H" for "high").
If $r=t$, we are done. If $r < t$, we recursively apply
the algorithm to input $(L,r)$; if $r > t$ we recursively
apply the algorithm to input $(H, r-t)$.
For this method to be efficient, we need to avoid that
either $t$ or $n-t$ is small. Specifically, we need
that for some positive constant $c$, we have
$cn \le t \le (1-c)n$.
Let $M$ be the set of these $n/5$ medians. Let $x$ be the median
of these medians. (If $|M|$ is odd, discard one of its elements
and then take the median.) Let $t=\rk(x)$. (This rank is with
respect to $B$, our original input.)
This is an example of bootstrapping: using a weaker result to
prove a stronger result without much effort. The original meaning
of the word "bootstrap" is a small loop at the back of a leather
boot that enables you to pull the boot on.
The term "bootstrapping" may have originated
with the fables of Baron Münchhausen (1785)
who supposedly lifted himself, and his horse,
out of a swamp by pulling his bootstraps.
(In the original, he was pulling his hair to the same effect.)
Class #9, Mon, Feb 1
All exercises are due Tue, Feb 9, except where stated otherwise.
Let $T$ be a rooted tree; let $L$ be the set of
leaves of $T$. For a node $v$ let $c(v)$ denote the number of
children of $v$. Let $P$ be a path from the root to a leaf $f$.
Let $\vol(P)=\prod_{x\in V(P)\setminus\{f\}} c(x)$ (so the product
extends over all nodes of the path $P$ except for the leaf at the end).
Prove: there exists a path $P$ from root to leaf such that $|L|\le \vol(P)$.
Infer from this that $d = \lfloor \log_2 n\rfloor$.
09.77 It is useful to split the UPDATE-KEY operation into
two types: DECREASE-KEY and INCREASE-KEY.
Do not use UPDATE-KEY; instead, use either DECREASE-KEY or INCREASE-KEY.
You may use the symbol $-\infty$ to denote a number that is smaller than
any key currently stored in $Q$.
So the command FINDMIN$(Q)$ can be executed in $O(1)$ steps.
(a) Write an elegant pseudocode for the
"bubbling up" routine that implements the $\decrease(v,\newkey)$ command
with as few comparisons as possible.
Bound the number of comparisons made by the the procedure
in terms of the depth or the height of the node $v$,
whichever is appropriate.
(b) Write an elegant pseudocode for the
"bubbling down" routine that implements the $\increase(v,\newkey)$ command
with as few comparisons as possible.
Bound the number of comparisons made by the the procedure
in terms of the depth or the height of the node $v$,
whichever is appropriate.
The point in both problems is that the update of the key
violates the Heap condition, which we then need to restore
without changing the topology.
In your pseudocode, use the link structure of the heap.
Do not use the arithmetic instructions of the array
implementation of the heap.
(b) Implement the INSERT command using
the DECREASE-KEY command once and $O(1)$ additional link updates.
You may use the symbol $\infty$ to denote a number that is greater
than any key currently stored in $Q$.
Give the best upper bound on the number of comparisons used
in terms of the appropriate parameter of the tree.
Prove the bound; you do not need to prove it is best.
Do not use asymptotic notation.
CLARIFICATION (added Feb 4, 3pm). In the spirit of the updated
description of linked lists (please, review: 05.03-05.07),
you may use additional links that are easy to maintain.
In particular, we may assume a link to the last node (node number $n$)
and for each node, a link to the preceding node and the next node
(in the level-by-level left-to-right order, which is the same as
the order in the array implementation of the heap.)
For "INSERT" we also need
to assume the topology is ready to receive an additional item.
This means a link to the (currently empty) node $n+1$ and the parent
link from node $n+1$ and the child link to node $n+1$ are also available.
(Much of this comes for free in the array implementation of the heap.)
UPDATE (Feb 4, 3pm). Mistakes in part (b) corrected.
The second phase will produce the data in non-decreasing order.
Hint: place the items in the heap backwards,
starting at position $n$. Use "bubbling down" as needed.
Use the fact that $\sum_{k=1}^{\infty} k/2^k = 2$.
WARNING: this is NOT a question about Heapsort. The algorithm has
random access to the data, it is allowed to compare any two of the items.
(The algorithm may ignore the heap or use some of the comparison
information encoded in the heap.)
Bookkeeping is free; this includes copying, comparing, and doing arithmetic
with addresses, recording the outcomes of previous comparisons, etc.
All computation is also free; this includes making the decision
what pair of items to compare next, based on the outcome of previous
comparisons.
[WARNING: This problem was updated Feb 8, 7:40pm and
deferred to Feb 16 from the original due date of Feb 9.
The update consists in the addition of the sentence beginning
"Moreover" below.]
Given $k$ sorted lists of data (real numbers), merge them into a single
sorted list using comparisons. Your algorithm should cost $O(k+n \log k)$
(including bookkeeping), where $n$ denotes 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. Moreover, for all $i\le n$,
the algorithm should produce the $i$-th item of the merged list
within time $O(k+i\log k)$, where "time $t$" means the first $t$ units
of cost incurred.
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 satisfy the complexity
(cost) bound stated.
Comment. Copying real numbers can be replaced by link
updates, so the only operation with real numbers that we need is comparison.
Class #8, Fri, Jan 29
All exercises are due Tue, Feb 2, except where stated otherwise.
(A) $\status(v)=\white$
(B) $\status(v)=\gray$
(C) $\status(v)=\black$
For each statement, decide whether it is a loop invariant.
Briefly reason your answers.
(D) The number of BLACK vertices increases.
(E) The number of BLACK vertices does not
decrease.
For each statement, decide whether it is a loop invariant.
Briefly reason your answers.
Class #7, Wed, Jan 27
All exercises are due Tue, Feb 2, except where stated otherwise.
The concepts you learn there include legal coloring of a graph,
$k$-colorability ($k$ colors suffice for a legal coloring),
chromatic number $\chi(G)$ (the smallest $k$ such that $G$ is
$k$-colorable), bipartite (2-colorable) graphs.
Let $\greedy(G)$ denote the number of colors used
by the greedy algorithm on the graph $G=([n],E)$. Prove:
$\greedy(G) \le 1+d_{\max}$ where $d_{\max}=\max_{v\in [n]}\deg(v)$.
The general case of the min-weight path problem
(negative weights permitted) is NP-hard, so
no polynomial-time algorithm can solve it unless P=NP.
If we permit negative-weight edges but no negative cycles
(cycles of negative total weight) then the problem can
be solved in polynomial time, although not as efficiently
as in the case of non-negative weights.
The essence of this statement is the "if" direction:
(*) Every DAG has a topological sort.
If $G$ has no edges then any ordering is a topological sort.
Assume now that $G$ has at least one edge, and therefore also
at least one vertex. Let $S$ denote the set of sinks of $G$.
Let $|S|=k$. By 07.42, $S$ is not empty, i.e., $k\ge 1$.
Let $H:=G[V\setminus S]$ be
the induced subdigraph on the complement of $S$. Now $H$ is
a DAG with $n-k < n$ vertices, so, by the inductive hypothesis,
$H$ has a topological sort $(v_1,\dots,v_{n-k})$. Let us add
the vertices of $S$ to this list in any order; what we get is
a topological sort of $G$. (Why?)
WARNING. A linear-time algorithm that is not based on the proof
above will not be accepted. Do not make your algorithm recursive;
expand the above proof into rounds such that in each round you
get an induced subdigraph and remove its sinks (if the subdigraph
has any sinks).
Let $s=1$ be the root. Solve the single-source min-weight path
problem in linear time. Prove the correctness of your algorithm.
State the critical loop invariants.
Hint. Simplify Dijkstra: replace the costly EXTRACT-MIN operations
with a simpler method of selecting the next vertex to be explored.
Class #6, Mon, Jan 25
All exercises are due Tue, Feb 2, except where stated otherwise.
(a) rooted traversal $\TRAV(G,v_0)$ is a process that
"discovers" all vertices accessible from the root
and "explores" all edges accessible from the root.
(b) full traversal $\TRAV(G)$ is a process that
"discovers" all vertices and "explores" all edges.
The generic notation "$\TRAV$" does not refer to a specific
process; we shall discuss several implementations of this concept.
(BFS, DFS, Dijkstra's algorithm, Jarnik's algorithm).
Throughout the traversal process, each vertex will have one
of three statuses: WHITE (unkown, not yet discovered),
GRAY (currently active, discovered but not finished),
BLACK (finished). Initially each vertex is WHITE.
For vertex $u$, let $d_u$ denote the time (step)
the discovery time and $f_u$ the finish time.
For a vertex that is not discovered in the process,
we set $d_u=f_u=\infty$. We have $d_u\le f_u$ for
every vertex. We assume that if $d_i <\infty$ then
$f_u <\infty$ (each vertex that is discovered at some
point will eventually be finished). Status changes are
irreversible: a GRAY vertex can never become WHITE
and a BLACK vertex cannot change its status. A vertex
$u$ is WHITE in the time interval $t < d_u$, GRAY in
the time interval $d_u\le t < f_u$, and black for
$t\ge f_u$.
An edge is either unexplored or explored.
Initially every edge is unexplored. "Exploration"
of the edge $u\to w$ occurs when $u$ is GRAY (active)
and the process checks the status of $w$. If it
finds that $w$ is WHITE, the process discovers $w$,
sets $d_w$ to the current time, and sets the parent link
to $p(w)=u$, indicating that $w$ was discovered while
exploring the edge $u\to w$. (Some traversal algorithms
(Dijsktra's, Jarnik's) may subsequently update the parent link,
assigning a "less expensive parent" to $w$, but here we discuss
the basic variant where these links, once assigned, stay fixed.)
Exploration of a given edge
occurs at most once in the process; from then on, the edge
has the status "explored." Once all edges from $u$ have been
explored, the status of $u$ changes to BLACK (finished) and
$f_u$ is set to the current time.
02
for $v\in V$
03
if $\status(v)=\white$ then
04
$\status(v):=\gray$, $d_v$ set to current time
(: $v$ discovered :)
05
$\TRAV(G,v)$
(b) Let $V_i$ denote the set of those vertices that are accessible
from $v_i$ but not accessible from any $v_j$ for $j\le i$. Then
(1) $v_i\in V_i$ (2) $\{V_0,\dots,V_k\}$ is a partition of $V$
(3) for all $w\in V_i$ we have
$d_{v_i} \le d_{w} < f_{w} < d_{v_{i+1}}$ (all vertices in $V_i$ are
finished before $v_{i+1}$ is discovered).
ATTENTION. The handout was updated on January 31 at 7:45pm.
Make sure to check that a footnote on the first page
states "Last updated 1-31-2021." If it does not, you are viewing
a cached prior version. If refreshing the browser does not help,
you may need to clear the browser's cache.
The update clarifies that time is discrete (a student
reported confusion about this issue) and in connection with this,
the update is more specific about what the "$t$-th time unit" means.
A terminological update: "speed vector" has been replaced by "velocity."
None of the updates affect the meaning of the problems assigned.
6.50 (a) Bonus (25 points, due Feb 9)
Solve problem (a) in the handout.
Give a clear description of the set $R$, describe the optimal
route, and prove its optimality. Structure your proof:
state lemmas that conceptualize what is happening and build
up to the proof. It should be clear from
your description that the optimal route visits a point 100 times.
2/3 of the credit goes for a clear description of $R$.
Vague or ambiguous descriptions will lose most of this credit.
6.50 (b) HW (16 points) Solve problem (b) in the handout.
(Somewhat efficient solution.) The set $R$ is given as a linked list of
its points. (A point is given as a pair of coordinates.) We use the
unit cost model: operations with numbers in the range $\{0,1,\dots, n\}$
(copying, incrementing or decrementing, using a number as an address)
have unit cost.
You may use algorithms discussed in class or in the exercises (HW, DO, Bonus)
before this one. Prove the complexity estimate.
A solution to (c) will not earn you credit for this
problem. Whatever you need to repeat, please do.
6.50 (c) Bonus (24 points) Solve problem (c) in the handout.
(Efficient solution.) Prove the complexity estimate.
If you need to repeat part of your solution to (b), please do.
Bear in mind that (b) and (c) might be graded by a different grader.
Class #5, Fri, Jan 22
All exercises are due Tue, Jan 26, except where stated otherwise.
Drawbacks of an array: (1) The array has
a fixed, predefined length. We usually need to initialize the entire
array before using it, so even if we actually only use a small number
of entries, we pay the price of the full length of the array.
(2)
Inserting an item into an array at a designated location or deleting
an item from the array are costly ($O(n)$) because
these operations require moving many other items (shifting them
to the left or to the right).
In a simple linked list, the items are arranged in a linear order,
and each item includes a link to the next item.
The first item is the head of the list, the last item is
the tail. A link to the list points to the head.
The "next" link from the tail is "NIL."
We can only move along a linked list one step at a time, unsing the
"next" link.
In a doubly linked list, each item also has a link to the preceding
item. In a circular linked list, we have a link from the tail
to the head, and in a circular doubly linked list we also have
a link from the head to the tail. In linear time, we can turn a simple
linked list into a circular doubly linked list. When we speak of
a linked list, it can refer to any of the types of linked
lists discussed. If necessary, we may assume that it is a circular
doubly linked list, but most algorithms in which we use lists
do not require moving backwards, and many do not require circularity
either. So we choose the simplest kind of linked list suited for the
application.
An important advantage of linked lists is that (1) they
do not have a fixed length and (2) adding or deleting an item at the end
or at the beginning of the list incurs only $O(1)$ cost (updating a constant
number of links); the same can be said about insertion and deletion
at any currently accessed location.
However, we cannot perform binary search on a linked list with sorted keys.
A queue can be implemented using a linked list with an additional
link from head to tail.
A stack can be implemented using a simple linked list.
(a) Edge-list representation. We list the edges as a linked list.
(b) Adjacency-list representation. Each cell $i$ in the array of
vertices points to a linked list, $\adj[v_i] =
[w_1, w_2, \dotsm, w_{k_i}]$, the adjacency list of $v_i$,
where $k_i = \deg^+(i)$ is the outdegree of $v_i$ and $w_1,\dots,w_{k_i}$
are the out-neighbors of $w_i$, listed in any order.
Note that upon reading the number $i$ we can immediately jump to
vertex $v_i$ in the array of vertices ("random access"),
and then start reading (in order) the outneighbors of $v_i$.
However, deciding whether $v_j$ is an
outneighbor of $v_i$ may take $k_i$ steps; we need to walk through all
outneighbors of $v_i$ before we can be sure that $v_j$ is not among them.
(a) Let $G$ be given in the edge-list representation. Convert
this into an adjacency-list representation of $G$ in linear time,
$O(n+m)$ where $m=|E|$. Operations with numbers $i\in [n]$ (reading,
copying) have unit cost. Describe your algorithm
in simple pseudocode. Give a brief reason why your algorithm
runs in linear time. You do not need to prove correctness.
(b) Let $G$ be given in adjacency-list representation.
Convert this into an edge-list representation of $G$ in linear time,
$O(n+m)$. The rules are the same as in part (a).
Solution
create the empty linked list $\adj^-[j]$
(: initializing the adjacency-array
representation of $G^-$ :)
end(for)
for $i=1$ to $n$
for $j\in \adj[i]$
(: visiting each out-neighbor of $i$ in the given order :)
append $i$ to $\adj^-[j]$
end(for)
end(for)
return $\adj^-$
Briefly reason why your algorithm is correct.
Briefly indicate why your algorithm runs in linear time.
For the latter, take 5.25 as a model.
You do not need to reason the correctness of your algorithm.
Please add one sentence to reason that it runs in linear time.
Take 5.25 as a model.
Class #4, Wed, Jan 20
All exercises are due Tue, Jan 26, except where stated otherwise.
Note that the exercises stated in Class #3 are also due Jan 26.
You do not need to reason the correctness of your algorithm.
Please add one sentence to reason that it runs in linear time.
Take 5.25 as a model.
BAC BAC
ACC BBA
BBA BBB
$M$ : = SORT $M$ by $j$-th column (: update $M$ :)
return $M$
The symbols of the alphabet $\Sigma$ are represented by the
integers $1,\dots,s$. We implement the SORT statement by
Counting-sort. Cost measure: operations on integers in the range
$1,\dots,\max\{n,s\}$ cost one unit. The operations include
arithmetic (incrementing), reading, copying. (Review Counting-sort).
The update of $M$ would require copying $M$ at a cost of
$\Theta(nk)$ in each round, at a total cost of $\Theta(nk^2)$,
which is not linear in the size of the input. Instead of
updating $M$, in each round we keep track of the permutation
of the rows (and do a last round of copying). This way
each round will incur a cost of $O(n+s)$ (counting sort),
at a total cost of $O((n+s)k)$. For $s=O(n)$ (which is the case
in most applications), this is linear in the size of the input
($nk$).
2 BAC 1 (BBB) 4 (BBA) 2 BAC
3 ACC 2 (BAC) 1 (BBB) 4 BBA
4 BBA 3 (ACC) 3 (ACC) 1 BBB
You do not need to reason the correctness of your algorithm.
Briefly reason the complexity estimate.
Take 5.25 as a model. Your solution to 4.32 will not earn you
credit for this problem. Your solution should be comeplete.
Example:
ABAAAAACA
ABB
BA
BAA
INPUT FORMAT. Each word
is given as a linked list of its characters.
Sample input:
2 BAA
3 AB
4 ABAAAAACA
5 BA
The OUTPUT (for this input) is the array $[3,4,1,5,2]$
indicating that the words come in this order. (This
describes the ordering of the words in Ex. 4.30.)
Write a reasonably elegant pseudocode.
Annotate your algorithm (explain what you do in each
nontrivial line). The length of
the input is $N=\sum_{i=1}^n (1+k_i)$ where $k_i$ is the length of
the $k$-th word.
Explain in words what your algorithm is doing.
Structure your algorithm for clarity. Give a complexity analysis.
Clarity and elegance count.
Complexity:
Your algorithm needs to run in time $O(N+sk_{\max})$
where $k_{\max}=\max_{i\in [n]} k_i$. Prove that your algorithm
satisfies this bound.
Class #3, Fri, Jan 15
HW and Bonus problems and DO exercises due Tue, Jan 26.
However, you need to study and understand the concepts and
the results regarding the Information Theory lower bound (3.10--3.16)
by Monday, Jan 18. It will be useful for some of the problems
that are due Tuesday, Jan 19. [These dates were previously posted
erroneously as Monday, Jan 20 and Tuesday Jan 21 -- such dates don't exist.]
Proof. First notice that we can assume that Bob asks exactly $m$
questions, regardless of the object $x$. Indeed, if Bob already
identified $x$ after fewer questions, he can continue to ask
dummy Yes/No questions.
Let $Q_1,\dots,Q_m$ be the questions asked by Bob and $A_1,\dots,A_m$
be Alice's answers. Bob's question $Q_i$ is determined by the history of
his communication so far with Alice, $(Q_1,A_1,\dots,Q_{i-1},A_{i-1})$.
Claim. $Q_i$ is determined by $(A_1,\dots,A_{i-1})$.
DO: Prove the Claim by induction on $i$.
The object $x$ is determined by the communication between Alice and Bob.
By the Claim, it follows that this entire communication is determined
by Alice's answer sequence, $(A_1,\dots,A_m)$. There are $2^m$
possible answer sequences, so there are $\le 2^m$ possible objects
Bob can identify. Therefore $N\le 2^m$. QED
Comment. This result cannot be inferred from Stirling's
asymptotic bound; we require this inequlity for all $n$, not just
for all "sufficiently large" $n$.
Hint. Your proof should be no just one line. Use the power series
expansion of $\eee^x$.
$(\log_2 \eee = 1.44269\dots) $.
(a) Use Ex. 3.25. Your proof should be very short.
Do not use Stirling's formula. Use results from ASY; state,
what results you are using. (b) Use Stirling's formula.
You do not need to reason the correctness of your algorithm.
Please add one sentence to reason the complexity estimate.
Take 5.25 as a model.
If $n=1$, return $A$.
Else let $A_1=A[1,\dots,\lfloor n/2\rfloor]$
and $A_2=A[\lfloor n/2\rfloor+1,\dots,n]$.
(: Note that $A_2$ has $\lceil n/2\rceil$ entries. :)
Return MERGE(SORT($A_1$), SORT($A_2$)).
Indeed, this follows from REV-INEQ Ex. 8, given that $C(1)=0$.
Given a list $A[1,\dots,n]$ of integers in the range $\{1,\dots,m\}$,
we can sort these integers in $O(n+m)$ steps.
The first phase of the algorithm counts the mutipicity (number of
occurrences) of each $j\in\{1,\dots,m\}$ in $A$. The output of this
phase is an array $B[1,\dots,m]$ where $B[j]$ is the multiplicity
of $j$ in $A$
$B[j]:=0$ (: initialize $B$ :)
for $i=1$ to $n$
$B[A[i]]++$ (: increment $B[A[i]]$ :)
return $B$
Given the array $B$ computed in the previous exercise,
compute the array $C:=$SORT($A$) (the list $A$ sorted).
Your computation should take $O(n+m)$ steps. Writing an integer
in the range $\{1,\dots,m\}$ counts as one step.
You do not need to reason the correctness of your algorithm.
Please add one sentence to reason the complexity estimate.
Take 5.25 as a model.
Class #2, Wed, Jan 13
HW and Bonus problems, STUDY and DO exercises due Tue, Jan 19 except
where otherwise stated.
Solving this problem will NOT earn you credit for the
preceding problem. For 02.10, follow the instructions
given there; give a simple solution.
(b) DO$^+$: Find an non-adaptive algorithm
for this problem, i.e., specify your measurements (subsets of coins
to put in each tray) in advance (your choice of which coins
must not depend on the outcomes of previous measurements).
Show that 3 measurements still suffice. Prove that your
solution is correct.
(a) HW
Prove that 3 measurements are not enough if $n = 14$.
Make your solution short and elegant. Elegance counts.
(b) Bonus
Prove that 3 measurements are not enough if $n = 13$.
Elegance counts. (A correct solution to part (b)
does not earn you the credit for part (a); you need to give
a very short direct solution to (a).)
Class #1, Mon, Jan 11
HW and Bonus problems due Tue, Jan 19 except
where otherwise stated. STUDY and DO exercises due earlier.
So the goal is to communicate few bits and at the same
time keep the error probability low.
They can accomplish both objectives using the Rabin protocol
that works as follows.
In the second case, Bob's declaration is simply a bet,
it may be in error: it is entirely possible that $X\neq Y$
but $X\equiv Y \pmod p$.
We shall show that if $k$ is slightly greater than $\log_2 n$ then the
probability that Bob's declaration is in error is small.
We shall make this statement precise below (Ex. 1.45).
Examples: $\nu(12)=2$, $\nu(720)=3$, $\nu(128)=1$,
$\nu(-20)=2$, $\nu(1)=0$, $\nu(0)=\infty$. DO: Verify
these values.
(a) Observe that $P(X,X)=0$.
(b) Assume now that $X\neq Y$. Then
$$P(X,Y) \le \frac{\nu(X-Y)}{\pi(2^k)}$$
where $\pi(x)$ denotes the prime counting function (see ASY).
(b) Infer that for all sufficiently large values of $k$ we have
$\displaystyle{\pi(2^k) > \frac{7}{5}\cdot\frac{2^k}{k}}$.
This exercise completes an analysis of the Rabin protocol: for $k$ as
stated in this exercise, $2k$ bits of communication suffice
to keep the probability or error asymptotically below $2^{-C}$.
This completes a stronger analysis of the Rabin protocol:
we got rid of the annoying $\log\log n$ term and still
reached the same performace guarantee.
View the instructor's
class material from previous years
Return to the
Department of Computer Science home page
Course home
Go to top