You may also use any result from the LinAlg book, except where the exercise is essentially identical with the result or a special case of the result from the book.

Presentation of algorithms [Added 2024-02-10 at 11:40am]

Material covered:   Approximation algorithms. Lattices in $\rrr^n$. The Lovász Lattice Transformation.

24.15 STUDY   LinAlg Chapter 19 (Euclidean spaces), especially Chapter 19.2 (Gram-Schmidt orthogonalization)

24.XX  

24.21 DEF (lattice)   Let $\bfv_1,\dots,\bfv_n$ be a basis in $\rrr^n$. The set of all integral linear combinations of the $\bfv_i$ is called an $n$-dimensional lattice with basis $\bfv_1,\dots,\bfv_n$. In other words, the lattice with basis $\bfv_1,\dots,\bfv_n$ is the set $$ {\calL} = \left\{\left.\sum_{i=1}^n \alpha_i \bfv_i \,\right|\, \alpha_i\in\zzz\right\}\,. $$ We say that $\calL$ is an integer lattice if all coordinates of each vector in $\calL$ are integers. For this it is necessary and sufficient that all vectors in a basis have integer coordinates.

24.23 DEF (Euclidean norm, orthogonality)   Let $\bfx=(x_1,\dots,x_n)$ and $\bfy=(y_1,\dots,y_n)\in\rrr^n$. The dot product of $\bfx$ and $\bfy$ is $\bfx\bfy := \sum_{i=1}^n x_iy_i$. The euclidean norm of $\bfx$ is $\|x\|:=\sqrt{\bfx\bfx}=\sqrt{\sum_{i=1}^n x_i^2}$. We say that $\bfx$ and $\bfy$ are orthogonal, denoted $\bfx\perp\bfy$, if $\bfx\bfy=0$.

24.25 (shortest vector problem, SVP)   Given a basis of a lattice $\calL$, we wish to find a non-zero vector with minimum norm $$\min\calL : = \min\{\|\bfx\| \,:\, \bfx\in\calL\setminus\{\bzo\}\}\,$$ For $C\ge 1$, a $C$-approximation to SVP is a non-zero lattice vector $\bfx\in\calL$ such that $\|\bfx\|\le C\cdot\min\calL$.

24.28 Theorem (László Lovász, 1984)   Given a basis for an $n$-dimensional integer lattice, a $2^{(n-1)/2}$-approximation to SVP can be found in polynomial time.

24.31 DO   Let $\bfv_1,\dots,\bfv_n$ be a basis of the lattice $\calL$. Let $\bfv_1^*,\dots,\bfv_n^*$ denote the Gram-Schmidt orthogonalization of this basis. Prove: there exist coefficients $\mu_{ij}\in\rrr$ for $1\le j\le i\le n$ such that for all $i$ we have $\mu_{ii}=1$ and $$ \bfv_i =\sum_{j=1}^i \mu_{ij} \bfv_j^* \,$$ Note. In this exercise and the next one, $\calL$ is any lattice, not necessarily an integer lattice.

One of the ingredients of the proof of Theorem 24.28 is the following lemma.

24.35 BON (16 points)   Let $\bfv_1,\dots,\bfv_n$ be a basis of the lattice $\calL$. Let $\bfv_1^*,\dots,\bfv_n^*$ denote the Gram-Schmidt orthogonalization of this basis. Prove: $$ \min\calL \ge \min_{1\le i\le n} \|\bfv_i^*\|\,.$$

24.XX  

24.XX  

24.XX  

More to follow. Please check back later.

Material covered:   Boolean circuits, SAT. Bit-complexity to circuit size. The Cook-Levin Theorem: SAT $\in$ NPC. 3SAT $\in$ NPC via SAT $\prec_{Karp}$ 3SAT. The 3DM (3-dim matching) problem. 3DM $\in$ NPC (stated). The SUBSET-SUM problem. SUBSET-SUM $\in$ NPC via 3DM $\prec_{Karp}$ SUBSET-SUM.

23.20 DEF   The integer knapsack problem (IKNAP) is the knapsack problem (see handout) with all weights, values, and the weight limit positive integers.

23.23 DEF   The decision version of the integer knapsack problem is the following.

• INPUT: $v_1,\dots,v_n,V,w_1,\dots,w_n,W$ positive integers. We refer to the $v_i$ as values, the $w_i$ as weights, $W$ the weight limit and $V$ the target weight.
• QUESTION: Can the target value be reached within the weight limit?
  In other words, does there exist $I\subseteq [n]$ such that
  • $\sum_{i\in I} w_i \le W$ and
  • $\sum_{i\in I} v_i \ge V$.

23.26 DO   Prove:   KNAP $\in$ NP. What is the witness?

23.29 DO   Prove that KNAP is Cook-equivalent to the integer knapsack problem. For the Cook reduction of integer knapsack to KNAP, use binary search. Prove that your reduction works in polynomial time.

23.32 ORD (8 points)   Prove:   KNAP $\in$ NPC.
For the proof, construct a Karp-reduction from some NP-complete language $L$ to KNAP. The language $L$ should be one of the following:
     SAT, 3SAT, CLIQUE, 3DM, SUBSET-SUM, 3COL, HAM.

23.35 DEF (PTAS)   Let $D$ be a non-empty finite set (the domain) and $f: D\to \rrr$ be an objective function that assigns positive values to each $x\in D$. The maximization problem for $x$ over $D$ seeks to maximize the value of $f(x)$ over $D$, i.e., it asks to find $y\in D$ such that $$ f(y)= OPT:= \max_{x\in D} f(x).$$ Some $x\in D$ is an $\epsilon$-approximate solution to this problem if $f(x) \ge (1-\epsilon)OPT$.
We typically consider infinite families of such maximization problems. (The Knapsack problem is such a family of problems). A polynomial-time approximation scheme for such a family of problems is an algorithm that for every $\epsilon > 0$ finds, in polynomial time, an $\epsilon$-approximate solution to each problem in the family.

23.38 BON (22+8 points) (PTAS for Knapsack)   (a)   Given $\epsilon > 0$, solve the Knapsack problem $\epsilon$-approxiately, using $O(n^3/\epsilon)$ steps. Here $\epsilon$ is a given positive real; the weights, values, and the weight limit are positive reals. The steps are: comparison of reals, arithmetic operations with reals, rounding of reals, comparison and arithmetic of integers, moving/copying integers.
The output must be a subset $I\subseteq [n]$ that satisfies the weight limit, and gets nearly optimal value.
  (b)   Show that for the integer knapsack problem, your solution gives a PTAS.
Hint for (a)   Do scaling and rounding for the values but not for the weights (because the weight limit must be observed exactly). Use the value version of the Dynamic Programming solution (BON 06.85).
Clarification [03-05 at 23:45] The problem you need to solve approximately is the original problem (max value under weight constraint). The hint does not change this, it only suggests that the value version (06.85) may help.

Material covered:   Conditional expectation. "Theorem of complete probability" for expected value. Independence of random variables. Expected value of independent r.v.'s. Positively, negatively correlated, uncorrelated random valiables. Complexity classes: P, NP. Puzzles whose solutions are polynomial-time verifiable.

20.15 STUDY   PROB 7.9 (random variables, expected value, indicator variables), PROB 7.10 (variance, covariance, Chebyshev's inequality), PROB 7.11 (independence of a pair of random variables), PROB 7.12 (independence of random variables).

20.18 ORD (10 points)   PROB 7.11.4 (uncorrelated but not independent random variables)

20.21 ORD (9 points, due Mar 6)   PROB 7.12.5 (functions of independent random variables)

20.XX  

Material covered:   Random variables. Expected value. Linearity of expectation. Indicator variables. Boolean variables, literals, disjunctive 3-clauses. MAX-3SAT problem.

Material covered:   Fast Fourier Transform. Finite probability spaces: events, conditional probability, independence of events.

18.XX  

18.15 DEF (DFT matrix)   Let $\omega$ be a primitive $n$-th root of unity. The DTF (Discrete Fourier Transform) matrix is the $n\times n$ complex matrix $F=(\omega^{ij})$ where $i,j=0,\dots,n-1$.

18.18 ORD (9 points, due Feb 29)   Prove: $F\cdot F^* = nI$, where $F^*$ denotes the conjugate-transpose of $F$.

18.23 ORD (7 points)   Assume the function $T:\nnn\to\rrr$ satisfies $T(n)\ge 0$ and $T(n) \le 2\cdot T(\lceil n/2\rceil)+O(n)$ for all $n\in\nnn$. Prove:   $T(n) = O(n\log_2 n)$. State the smallest value you can prove for the constant hidden in the $O(n\log_2 n)$ term in terms of the constant hidden in the $O(n)$ term.

18.XX  

Material covered:   Bit-length of determinant. Permanent. Edmonds: Gaussian elimination in polynomial time. Fast multiplication of polynomials and of integers. The $\log^*$ function. Complex $n$-th roots of unity. Discrete Fourier transform. Inverse DFT. Convolution.

17.31 DO (bit-length of integers)   If $n\in\nnn$ then the bit-length of $n$ is $b(n) =\lceil \log_2 (n+1)\rceil$.
Proof.   If $b(n)=k$ then $2^{k-1} < n+1 \le 2^k$.

17.34 DEF (bit-length)   We define $b(0):=1$, $b(-n):=b(n)$. For rational numbers $b(r/s):=b(r)+b(s)$ where $\gcd(r,s)=1$. For matrices $A=(a_{ij})$ over the rationals, we define $b(A):= \sum_i \sum_j b(a_{ij})$.

17.37 Theorem (bit-length of determinant)   Let $A$ be an $n\times n$ integral matrix (all entries integers). Then   $b(\det(A)) \le b(A)$.

17.39 DO   Let $x_i \ge 0$. Then $$ \prod_{i=1}^n (1+x_i) \ge 1+\sum_{i=1}^n x_i$$ and $$ \prod_{i=1}^n (1+x_i) \ge 1+\prod_{i=1}^n x_i$$

17.42 DEF (permanent)   Let $A=(a_{ij})$ be an $n\times n$ matrix. Then the permanent of $A$ is defined as $$ \per(A) = \sum_{\sigma\in S_n} \prod_{i=1}^n a_{i,\sigma(i)}\,.$$ This is the same definition as the determinant except no signs are attached to the expansion terms.

17.45 DO   Let $A$ be the bipartite adjacency matrix of a bipartite graph $G$ where each side has $n$ vertices. Then $\per(A)$ is the number of perfect matchings of $G$.

17.48 Theorem (Leslie G. Valiant, 1979)   Computing $(0,1)$-permanents (permanents of $(0,1)$-matrices) is $\#P$-complete, meaning that it is equivalent, via a polynomial-time reduction, to counting 3-colorings of a graph.
So this problem seems much harder even than NP-complete problems such as deciding 3-colorability of a graph.

17.51   Let $A$ be an $n\times n$ real matrix. Then $|\per(A)| \le \prod_{i=1}^n \|\bfa_i\|_1$ where $\bfa_i$ denotes the $i$-th row of $A$ and $\|\bfx\|_1=\sum_{i=1}^n |x_i|$ denotes the $\ell_1$-norm of the vector $\bfx=(x_1,\dots,x_n)$.

17.54 DO   Let $A=(a_{ij})$ be an $n\times n$ real matrix. Let $B=(b_{ij})$ where $b_{ij}=|a_{ij}|$ and let $C=(c_{ij})$ where $c_{ij}=\max\{1, b_{ij}\}$ (so all zero entries of $B$ are replaced by 1 in $C$). Then $b(A) = b(B) = b(C)$, while $|\det(A)|\le \per(B) \le \per(C)$.

17.57 ORD (3+4 points)   Consider the following statement:
   $(*)$   For a matrix $C$ with positive integer entries, $b(\per(C))\le b(C)$.
   (a)   Show that Theorem 17.37 follows from $(*)$.
   (b)   Show that $(*)$ follows from the next exercise.

17.59 ORD (8 points)   Let $C=(c_{ij})$ be an $n\times n$ matrix with non-negative real entries. Prove that $$ 1+\per C \le \prod_{i=1}^n \prod_{j=1}^n (1+c_{ij}) $$ Use some of the exercises above; at each step, state which exercise you are using, in what roles for the variables.

17.62 DO (Gaussian elimination works in polynomial time) (Jack Edmonds, 1965)   Let $A\bfx = \bfb$ be a system of $k$ linear equations in $n$ unknowns (so $A$ is a $k\times n$ matrix). Assume all entries of $A$ and $\bfb$ are integers. Let $A'$ be the matrix $[A|\bfb]$ (added the right-hand side as a column to $A$).
Let us perform a sequence of row-operations on $A'$ that are steps in the Gaussian elimination process. Show that each entry in the resulting matrix is a quotient of the determinants of submatrices of $A'$.

17.XX  

Material covered:   Proof of Polynomial Identity Lemma. Application: deciding whether a bipartite graph has a perfect matching.

16.15 STUDY   the recently added paragraph above titled "Presentation of algorithms".

16.21 Polynomial Identity Lemma (Øystein Ore, 1922)   Let $F$ be a field, $H\subseteq F$ be a finite subset of size $h$, and let $f\in F[x_1,\dots,x_n]$ be a nonzero polynomial of degree $d$ in $n$ variables. Then $$ \Pr_{\bfa\in H^n} (f(\bfa)=0) \le \frac{d}{h}\,. $$ Here the probability is over the uniform distribution. In other words, if $A=\{\bfa\in H^n \mid f(\bfa)=0\}$ then $$ |A| \le d\cdot h^{n-1}\,.$$

16.24 History   Norwegian mathematician Øystein Ore (1899--1968) proved this result in a number theoretic context. The lemma was rediscovered several times, including in the theory of error correcting codes in 1954 (Reed--Muller codes) and most recently independently by Jacob Schwartz and Richard Zippel in 1979 in the context of randomized algorithms. This last rediscovery turned out to be highly influential, with thousands of citations. While number theorists have all along been aware of Ore's paper and cited it in monographs, Ore's paper was only recently "discovered" in the theory of computing community where for decades the result has been cited as the "Schwartz--Zippel lemma."

16.27 DO   Prove the PIL by induction on $n$.
(Or check the proof on the SLIDES.)

16.31 DO   Prove that this bound is tight in the following sense. For every field $F$ and every triple $(n,d,h)$ of positive integers such that $d\le h\le |F|$ and for every finite subset $H\subseteq F$ of size $|H|=h$, there exists a nonzero polynomial $f\in F[x_1,\dots,x_n]$ of degree $d$ such that $$ \Pr_{\bfa\in H^n} (f(\bfa)=0) = \frac{d}{h}\,. $$

16.34 Polynomial Identity Testing (PIT)   Let $F$ be a field and $f\in F[x_1,\dots,x_n]$ a polynomial of degree $\le d$, possibly the zero polynomial. We are given a black box that on input $\bfa\in F^n$ returns $f(\bfa)$. We wish to decide whether $f=0$ (the zero polynomial).

16.37 PIT black-box algorithm   Assume $|F|\ge 2d$.
01     select $H\subseteq F$ such that $|H|\ge 2d$
02     select $k\in\nnn$        (: $2^{-k}$ is our error tolerance:)
03     for $i=1$ to $k$ do
04          pick $\bfa\in H^n$ uniformly at random
05          if $f(\bfa)\neq 0$ then return "$f\neq 0$"
06          end(if)
07     end(for)
08     return "$f=0$"

16.41 DO (probability of error)   Observe:   (a)   If $f=0$ then the algorithm always returns the correct answer (error probability 0)
    (b)   If $f\neq 0$ then the probability of an erroneous answer is $\le 2^{-k}$.

16.44 DO   Notice that if the algorithm answers "$f\neq 0$" then it also supplies a proof of the validity of this answer: a witness $\bfa\in H^n$ such that $f(\bfa)\neq 0$.

16.48 ORD (4 points)   Consider the following statement:

   (*)     If the black-box PIT algorithm answers "$f=0$" then this answer is correct with probability $\ge 1-2^{-k}$.

Demonstrate that this statement is false.
Do this in the following model. $F$ is a field in which we can perform computation. We choose a parameter $d\ge 1$ such that $|F|\ge 2d$. A polynomial $f\in F[x_1,\dots,x_n]$ is brought to us by an honest adversary. The adversary presents the polynomial as a black box, to which we are allowed to make $k=10$ queries. The adversary guarantees that the degree of the polynomial is at most $d$. We use our allotment of queries to perform the black-box PIT algorithm with error tolerance $2^{-k}$.

For a compelling refutation of (*), devise an adversary strategy under which the conditional probability $\Pr($answer correct$\mid$answer is "$f=0$"$)$ is zero.

16.XX  

16.61 DEF   A perfect matching in a graph $G$ is a matching with $n/2$ edges (so all vertices are matched).
Note that in order to have a perfect matching, $n$ must be even.

16.64 DEF   Let $G=(V,E)$ be a bipartite graph with $V=U\cup W$ the partition of $V$ such that all edges pass between $U$ and $W$. Let $|U|=k$ and $|W|=\ell$; let $U= \{u_1,\dots,u_k\}$ and $W=\{w_1,\dots,w_{\ell}\}$. Let $B_G=(b_{ij})$ denote the $k\times \ell$ $(0,1)$ matrix where $b_{ij}=1$ if $u_i \sim w_j$ and $b_{ij}=0$ otherwise. We call $B_G$ the bipartite adjacency matrix of $G$.

16.67 DO   Let $G$ be a bipartite graph with $n=2k$ vertices, $k$ in each part. So the bipartite adjacency matrix $B_G$ is a $k\times k$ matrix. Prove:   (a)   If $\det B_G\neq 0$ then $G$ has a perfect matching.   (b)   The converse is false.

16.71 DEF   Let $G$ be a bipartite graph. Let us replace each entry of 1 in the bipartite adjacency matrix $B_G$ by a distinct indeterminate, so the nonzero entries are $x_1,\dots,x_m$ where $m=|E|$. Call the resulting matrix the generic bipartite adjacency matrix of $G$. (This is not a generally accepted term.) Denote this matrix by $\Bhat_G[x_1,...,x_m]$.

16.74 DO   Let $F$ be a field. Let $G$ be a bipartite graph with equal-sized parts. Prove: $G$ has a perfect matching if and only if $\det(\Bhat_G)\neq 0$. Here $\det(\Bhat_G)$ is interpreted as a polynomial in $m$ variables over $F$.

16.76 Theorem (Chebyshev)   For every integer $m\ge 2$ there exists a prime $p$ such that $m\le p < 2m$.

16.77 DO (bipartite perfect matching via PIT)   Use PIT to decide whether a given bipartite graph $G$ has a perfect matching.
To avoid having to deal with large numbers, select a prime $p$ such that $2n\le p < 4n$ (by Chebyshev's theorem 16.76, such a prime always exists) and work over the field $\fff_p$. Apply black-box PIT to the generic bipartite adjacency matrix of $G$.
The complexity of this algorithm depends on how fats we can compute the determinant. Gaussian elimination requires $\Theta(n^3)$ arithmetic operations. Strassen has shown that this can be reduced to $O(n^{\beta})$ where $\beta = \log_2 7 = 2.807\dots$.

16.81 DO (efficency)   Let us compare the efficiency of Kőnig's deterministic algorithm with the PIT-based algorithm with error tolerance $10^{-6}$.
Kőnig's algorithm costs $O(nm)$ in the uniform model (where $m$ is the number of edges) (13.54, 13.56). What is the cost of the PIT-based algorithm (using Strassen multiplication)? For what graphs does the latter outperform the former? Use bit-complexity for the comparison (so you have to convert Kőnig's cost estimate from uniform to the bit model).
Update [Feb 24 at 22:00] Previously posted as ORD.

16.84 BON (12 points)   Let $F$ be any field. For a bipartite graph $G$, prove that the matching number of $G$ (size of its maximum matching) is the rank of its generic bipartite adjacency matrix over the field $F(x_1,\dots,x_m)$ (the field of quotients of polynomials in these variables).

16.87 BON (7+8+12) (matching number via PIT)   Let $F$ be any field and $G$ a bipartite graph with matching number $\nu(G)$. Prove:
    (a)   for any $\bfa\in F^m$ we have $\rank(\Bhat_G(\bfa)) \le \nu(G)$
    (b)   Let $H$ be a finite subset of $F$ of size $|H|\ge 2\nu(G)$. Prove: $$\Pr_{\bfa\in H^m}(\rank(\Bhat_G(\bfa)) = \nu(G))\ge 1/2$$     (c)   Turn this result into an efficient algorithm to compute the matching number with error tolerance $2^{-k}$. Describe your algorithm in pseudocode. (Read the recently added comments regarding pseudocode at the end of the preamble at the top of this page.)
Use a field $\fff_p$ where $2\ell \le p < 4\ell$ where $\ell=\min(|U|,|W|)$, where $U$ and $W$ are the two parts of $V$. Justify this choice. Estimate the bit-complexity of the algorithm. Your estimate should be of the form $O(n^c (\log n)^d)$ where $n$ is the number of vertices of $G$ and $c$ and $d$ are constants. Give your smallest value of $c$, and for that $c$, your smallest value of $d$. Do not use fancy matrix multiplication and the like, just Gaussian elimination to determine rank.
Clarification [added 2-18 at 17:45]   Include an algorithm to find the prime $p$. Nothing sophisticated; do not use any results we have not discussed in class, other than Chebyshev's theorem 16.76. You need to give a rough estimate of the cost of finding such a prime $p$. Your estimate should be strong enough to show that this is a negligible part of the overall cost of the algorithm. --- The constant hidden in the big-Oh notation in the complexity of the algorithm depends on $k$. Make this dependence explicit. So your complexity bound should more properly be of the form $O(f(k)n^c (\log n)^d)$ where $f(k)$ is a function of $k$; minimize $f(k)$ along with the constants $c$ and $d$. --- "Error tolerance" means an upper bound on the probability that the algorithm returns an incorrect answer.

16.XX  

16.100 (Edmonds's blossom algorithm, 1965)   finds a maximum matching in a graph in $O(n^2m)$. (Here we are talking about all graphs, not just bipartite graphs.)

Material covered:   Elements of abstract algebra: binary operation, commutative ring, field. Finite fields. Polynomial in a single variable. Polynomial function. Roots, corresponding factors. Multivariate polynomials, monomials, degree, individual degree. Polynomial Identity Testing, Polynomial Identity Lemma.

Material covered:   Independence number $\alpha(G)$, chromatic number $\chi(G)$ of graphs. Chromatic number as a conflict model. Greedy coloring algorithm. Gaussian elimination.

14.10 STUDY   the greatly expanded material under Class #13 (below)

14.20 STUDY   Graph Theory terminology DMmini 6.1 (entire chapter)

14.23 STUDY especially   Terminology DMmini 6.1.1 (bipartite graphs), 6.1.16 (spanning subgraph, induced subgraph), Terminology 6.1.42 (clique number $\omega(G)$, independence number, chromatic number).

14.28 STUDY   Greedy coloring algorithm handout

14.31 ORD (8 points, due Feb 22)   Let $k(G)$ denote the number of connected components of the graph $G$. Given the graph $G=(V,E)$ where $V=[n]$, find, in linear time (in the unit cost model) the number $k(G)$, and produce an array of $k(G)$ monotone lists that list the vertices of each connected component.
Write a simple pseudocode. Include all details that come from BFS.

14.34 DO   DMmini 6.1.19 (number of induced subgraphs, number of spanning subgraphs)

14.36 DO   (a)   $\alpha(G) =\omega(\Gbar)$   (b)   $\chi(G) \ge \omega(G)$.

14.39 DO   DMmini 6.1.50 graph bipartite $\iff$ 2-colorable

14.41 DO   DMmini 6.1.22 (bipartiteness of paths, cycles)

14.44 DO   DMmini 6.1.23 (bipartite $\iff$ no odd cycle)

14.47 ORD (10 points, due Mar 6)   Given a graph $G$, decide, in linear time, whether it is bipartite. If it is bipartite, produce a 2-coloring in linear time (a $(0,1)$-array $C$ of length $n$ where $C[i]=0$ or $1$ depending on the color of vertex $i$). If it is not bipartite, find an odd cycle in linear time, represented as a list of distinct vertices, each of which is adjacent to the next vertex, and the last vertex is adjacent to the first. Give a clear, well-structured and explained pseudocode, with reference to algorithms discussed in class or lower-numbered exercises.

14.51 ORD (5 points)   DMmini 6.1.56   (chromatic number vs. independence number)

14.54 DO   Greedy coloring handout problem (a) (greedy uses $\le 1 + \Delta(G)$ colors where $\Delta(G)$ is the maximum degree).

14.58 ORD (6+5+7 points)   Greedy coloring handout problems (b), (c), (d) (greedy terrible, greedy can be optimal, linear-time implementation of greedy coloring in the unit cost model)

14.61 BON (10 points)   Let $G$ be a triangle-free graph. Show that $\chi(G) = O(\sqrt{n})$. Give an algorithmic proof, i.e., an algorithm that uses only this many colors. Describe your algorithm in simple and well explained pseudocode. State the smallest constant for which you can prove that your algorithm uses $\le c\sqrt{n}$ colors for all sufficiently large $n$.

14.64 DO   DMmini 6.1.58 (chromatic number vs. clique number)

14.67 ORD (10 points, due Feb 29)   DMmini 6.1.59 (triangle-free graph that is not 3-colorable). Do not prove that your graph is triangle-free but do prove that it is not 3-colorable.

14.71 CH   DMmini 6.1.60 (triangle-free graph with arbitrarily large chromatic number)

14.74 ORD (7 points)   Let $G=(V,E)$ be a non-empty regular graph (i.e., $E\neq\emptyset$). Prove:   $\alpha(G) \le n/2$. Generalize the method shown in class to prove that $\alpha(C_n) \le n/2$. (See SLIDES, Feb 5 lecture.)

14.79 BON (9+7 points)   (a)   Let $A$ denote the adjacency matrix of the graph $G$ (DMini Def. 6.4.9). (Note that for graphs this is a symmetric matrix with an all-zero diagonal.) Prove: the number of triangles in $G$ is $C\cdot \trace(A^3)$ where $C$ is a constant and $\trace$ denotes the trace (the sum of the diagonal elements.) Determine $C$. (Note: $C$ is not a bound but an exact value.)   (b)   Assume the graph $G$ is given by its adjacency matrix. Count the triangles in $O(n^c)$ time in the bit model, for some constant $c < 3$. Find the smallest constant $c$ for which you can prove this bound. Note that we are NOT using the unit cost model in this problem.

14.XX  

14.XX  

More to follow. Please check back later.

Material covered:   Fredman-Tarjan trees. Min-weight spanning tree problem. Kruskal's (greedy) algorithm. Jarník-Prim algorithm. Reverse greedy (pessimist's) algorithm. Matching. Maximal vs maximum. Kőnig's maximum matching algorithm for bipartite graphs: augmenting paths.

13.20 STUDY   Greedy matching algorithm handout

13.29 Notation   Let $T$ be a rooted tree and $v\in V(T)$. We shall write $\chld_T(v)$ to denote the number of children of $v$, or simply $\chld(v)$ if $T$ is clear from the context. If $r$ is the root of $T$ then we shall call $\chld(r)$ the root-degree of $T$.

13.31 DEF   A Fredman-Tarjan tree is a rooted tree $T$ such that for every vertex $v\in V(T)$ if $w_1,\dots,w_k$ are the children of $v$ arranged such that $\chld(w_1)\le \dots \le \chld(w_k)$ then $(\forall i\in [k])(\chld(w_i) \ge i-2)$.
The connected components of the rooted forest holding the data in the Fibonacci heap are Fredman-Tarjan trees.

13.34 ORD (7+4 points)   Recall that we write $\nnn_0$ to denote the set of non-negative integers. For $k\in\nnn_0$, let $g(k)$ denote the minimum number of vertices of a Fredman-Tarjan tree with root-degree $k$. So $g(0)=1$, $g(1)=2$, $g(2)=3$. (Check!).   (a)   Determine $g(k)$. Your answer should be very simple; make sure it is accurate.   (b)   Infer from your answer that if $T$ is a Fredman-Tarjan tree with $n$ vertices then its root-degree is $O(\ln n)$. Determine the smallest constant hidden in the big-Oh notation.

13.41 Notation   The matching number (maximum number of disjoint edges) of the graph $G$ is denoted $\nu(G)$. The symbol $\nu$ is the Greek letter "nu", in LaTeX "\nu".

13.44 ORD (5+5 points)   Let $G$ be a graph and $M$ a maximal matching of $G$.   (a)   Prove:   $|M| \ge \nu(G)/2$.   (b)   Show that this bound is tight in the following sense: for every $k\in\nnn$ there is a connected bipartite graph $G$ satisfying $\nu(G)=2k$ and a maximal matching $M$ in $G$ such that $|M| = k$. Clarity of the description of your graphs $G$ is paramount.

13.47 DO   Show that the greedy matching algorithm always produces a maximal matching. Therefore, the greedy matching algorithm is a $(1/2)$-approximation algorithm for the maximum matching problem.

13.51 DEF   Let $G=(V,E)$ be a graph and let $M\subseteq E$ be a matching. Let $P$ be a path of length $k$ in $G$, viewed as a list of edges, $P=[e_1,\dots,e_k]$ (in this order). We say that $P$ is an augmenting path for $M$ if $k$ is odd, $e_2, e_4,\dots, e_{k-1}\in M$, and $e_1$ and $e_k$ reach unmatched vertices, i.e., $e_1, e_k\not\subseteq \bigcup \{e\mid e\in M\}$.
By switching the augmenting path we mean to take the symmetric difference $M' = (M\setminus P)\cup (P\setminus M)$ (where $P$ is viewed as a set, rather than a list, of edges). In other words, we replace, in $M$, the even-numbered edges of $P$ (which belong to $M$) by the odd-numbered edges of $P$. This is again a matching (check!).
This way we replaced $(k-1)/2$ edges by $(k+1)/2$ edges, increasing the size of $M$.

13.54 BON (18 points, due Feb 22)   Let $G$ be a graph and $M$ a matching. If $M$ is not maximum then there exists an augmenting path.

The following algorithm is now immediate.

01     $M=\emptyset$        (: $M$ will become our maximum matching :) (: loop invariant: $M$ is a matching :)
02     while an augmenting path exists
03        find one
04        switch
05     end(while)
06     return $M$

The difficulty lies in implementing lines 02-03. Hungarian mathematician Dénes Kőnig invented the method of augmenting paths, and solved the problem of constructing them for bipartite graphs. This was one of a small number of results that inaugurated the theory of combinatorial optimization. (There is a lot more to Kőnig's result than this algorithm; the original paper was also one of the originators of combinatorial duality theory, a theory at the heart of combinatorial optimization.)

13.56 ORD (10 points)   Let $G$ be a bipartite graph and $M$ a matching in $G$. In linear time, decide, whether an augmenting path exists, and if it does, find one. Your algorithm should be very simple, a single application of BFS. The main question is, to what digraph to apply BFS.

13.58 COROLLARY (Kőnig, 1930)   In a bipartite graph, a maximum matching can be found "efficiently."
The concept of "polynomial time" did not exist back then, but we can now say that Kőnig's algorithm runs in polynomial time, specifically, in time $O(n(m+n))$: there are $O(n)$ rounds, each executed in linear time.

13.62 Maximum matching for general graphs (Jack Edmonds, 1965)   Nearly four decades after Kőnig, Canadian mathematician Jack Edmonds designed a polynomial-time algorithm for maximum matching of general (not necessarily bipartite) graphs, as an early demonstration of the power of the then new notion of polynomial time which he had just invented.

This brief historic account indicates the profound influence the study of maximum matchings exerted on the theory of algorithms.

13.XX  

13.69 DEF   The maximum weighted matching problem takes as input a graph $G=(V,E)$ and a weight function $w:E\to\rrr$ with non-negative weights $w(e)$ and asks for a matching of maximum total weight.

13.72 greedy matching algorithm for edge-weighted graphs:
   sort the edges by weight:   $w(e_1)\ge \dots \ge w(e_m)$
   $I:=\emptyset$     (: $I$ collects the indices of the selected edges :) (: loop invariant: the set $\{e_i\mid i\in I\}$ is a matching :)
  for $i=1$ to $m$
         if $e_i$ does not intersect $\bigcup_{j\in I} e_j$ then add $i$ to $I$
  end(for)
  return $M:=\{e_i\mid i\in I\}$

13.75 BON (12 points)   Show that the greedy matching algorithm for edge-weighted graphs is a $(1/2)$-approximation algorithm for the maximum-weight matching problem, i.e., it produces a matching of which the weight is at least $1/2$ of the maximum-weight matching.
Give a very simple proof. Elegance counts.

13.XX  

13.79 DEF   Let $G=(V,E)$ be a connected graph and $w:E\to\rrr$ a weight function. (The weights can be negative.) The weight of a subgraph is the sum of the weights of its edges. We wish to construct a minimum-weight spanning tree of $G$.

The following "purely greedy" algorithm was designed by American mathematician Joseph Kruskal in 1956.

13.82 (Kruskal's algorithm)
01     sort the edges:   $w(e_1)\le \dots \le w(e_m)$
02     $F:=\emptyset$        (: loop invariant: $F$ is a forest:) (: $F$ collects the edges of the spanning tree :)
03     for $i=1$ to $m$
04              if $e_i$ connects two components of $F$ then add $e_i$ to $F$
05     end(for)
06     return $F$

13.85 Reward problem   Prove that this algorithm produces a minimum-weight spanning tree.

13.88   The implementation raises a delicate data structure issue: how do we maintain the connected components of $F$. We shall deal with this later.

13.91 Jarník's algorithm   Decades before Kruskal, Czech mathematician Vojtěch Jarník (1930) developed a different greedy approach: growing the tree from a source node, à la Dijkstra (or more properly we should say, Dijkstra works à la Jarník). In 1957, American mathematician Robert C. Prim rediscovered Jarník's algorithm, and for decades the algorithm has been referred to as Prim's algorithm.

Here is a high-level description of Jarník's algorithm.

Input: a connected graph $G$
01     select "source" vertex $s$
02     $F:= \emptyset$        (: $F$ grows the edges of the spanning tree :) (: loop invariant: $F$ forms a tree rooted at $s$ :)
03     while $F$ has not reached all vertices of $G$
04        let $e$ be the lightest edge that connects a vertex of the tree defined by $F$ with a vertex not yet reached by $F$
05        add $e$ to $F$
06     end(while)
07     return $F$

13.94 ORD (7+4 points)   The delicate issue here is implementing line 04.
It turns out that this can be accomplished by copying Dijsktra's algorithm from the handout almost verbatim, with only a tiny change in the RELAX routine.
  (a)   Describe the updated RELAX routine
  (b)   Explain the new meaning of the quantities $t(v)$ and the parent links
[Clarification added Feb 13 at 13:50.]   You are not required to prove that your answers to (a) and (b) actually work. But the answers should be simple.

13.XX  

13.XX  

More to follow. Please check back later.

Material covered:   Reviewed Heap implementation of Priority Queue (see slides of previous class). Array implementation of balanced binary tree. HEAPIFY: building heap out of a given list of data, making $O(n)$ comparisons. Cost of Dijkstra depending on the implementation of the Priority Queue: via HEAP and via Fibonacci heap. Parameters of Fibonacci heap, amortized cost of data structure operations. Spanning subgraph, spanning tree.

12.15 STUDY   Amortized complexity handout

12.21 DO   If $|x| <1$ then $$\sum_{k=1}^{\infty} kx^{k-1} = \frac{1}{(1-x)^2}\,. $$

12.21 DO   HEAPIFY: Given a list of $n$ data (reals), organize them in a heap. Starting from an empty heap and performing repeated INSERTs requires bubbling up for each item; this requires $\sim \sum_{i=1}^{n-1} \log_2 i = \log(n!) \sim n\log n$ comparisons.
Theorem.   HEAPIFY can be performed making $O(n)$ comparisons.

Proof.   Since $n$ is known, the topology is known. Fill out the balanced binary tree with $n$ nodes bottom-up. With each item added, we need to bubble down. If the depth of the tree is $d$ then bubbling down an item at depth $d-i$ makes $\le 2i$ comparisons. (The root is at depth zero.) The number of nodes at depth $k\ge 0$ is at most $2^k$. So the total number of comparisons made is at most $$ \sum_{i=0}^d 2^{d-i}\cdot 2i < 2^d \sum_{i=1}^{\infty}\frac{i}{2^{i-1}} = 4\cdot 2^d < 4n\,.$$

12.25 DO   The cost of Dijkstra's algorithm in terms of Priority queue requests is

•    INSERT                    $\le n$ times    (actually $n_0$ times, where $n_0$ is the number of vertices accessible from the root)
•    EXTRACT-MIN      $\le n$ times    (again, actually $n_0$ times)
•    DECREASE-KEY   $\le m$ times    (actually, $m_0$ times where $m_0$ is the number of edges starting at an accessible vertex)

12.28 DO   In the HEAP implementation of the Priority queue, the cost of each of the three Priority-queue requests listed is $O(\log n)$ comparisons, so the total number of comparisons made by Dijkstra's algorithm with the HEAP implementation of the Priority queue is $O((n+m)\log n)$.

12.31 (Fibonacci heap 1, Michael Fredman--Robert E. Tarjan 1984)   In the Fibonacci heap implementation of the Priority queue, the number of comparisons required for the basic Priority queue requests is

•    INSERT                    $O(1)$
•    EXTRACT-MIN      $O(\log n)$
•    DECREASE-KEY   $O(1)^*$

12.34 DEF (amortized cost)   A dynamic set $S$ of data is a set of items that can change in the course of the execution of an algorithm; the changes occur by serving the requests INSERT(key), DELETE(item), INCREASE-KEY(item, key), DECREASE-KEY(item, key). Assume a data structure serves requests $T_1,\dots,T_k$ that include the INSERT operation and the creation of the empty set. Let us assign a number $c_i \ge 0$ to request $T_i$; $c_i$ may depend on $n:=|S|$. We say that $(c_1,\dots,c_k)$ constitute a valid amortized cost assignment to these requests if for any sequence $Q_1,\dots,Q_m$ of requests $Q_j\in\{T_1,\dots,T_k\}$ applied to the dynamic set $S$, starting with $S=\emptyset$, the actual cost of serving this sequence of requests is not greater than $\sum_{j=1}^m d_j$ where $d_j=c_i$ if $Q_j=T_i$. In other words, if we pretend that each service of request $T_i$ costs $c_i$, we shall end up with an upper bound on the actual cost.

12.37 DO   The total number of comparisons made by Dijkstra's algorithm with the Fibonacci Heap implementation of the Priority queue is $O(n\log n+m)$.

In the next sequence of exercises we show that Fibonacci heap is an optimal implementation (within a constant factor) of Priority queue for Dijkstra's algorithm.

12.41 DO   Let $G=(V,E)$ be a digraph without self-loops (adjaceny is an irreflexive relation) and $s\in V$ such that every vertex of $G$ is accessible from $s$. Then Dijkstra's algorithm will make at least $m$ comparisons, where $m$ is the number of edges.

12.44 DO (sorting via Dijkstra)   Given $n$ and $m$ where $n-1\le m\le n^2-n$, there exists a digraph $G=(V,E)$ with $n$ vertices and $m$ edges, without self-loops, and a vertex $s\in V$ from which all vertices of $G$ are accessible, such that the following holds.
Given a list $[a_1,\dots,a_{n-1}]$ of non-negative real numbers, we can use these data to assign non-negative weights to each edge of $G$ such that the list of min-costs of the vertices will be the given list, and order in which Dijkstra's algorithm finishes the vertices will produce these costs in sorted order.
Hint.   First solve the case $m=n-1$.

12.47 DO   Infer from the preceding exercise that for the digraph $G$ with source vertex $s$, there exists a weight assignment to the edges such that Dijkstra's algorithm will require $\ge \log_2((n-1)!)\sim n\log_2 n$ comparisons regardless of the implementation of the priority queue.

12.51 DO   Infer that the Fibonacci heap implementation of the Priority queue is optimal within a constant factor with respect to the number of comparisons, i.e.,
For any $n$ and $n-1\le m\le n^2-n$ there exists a digraph $G=(V,E)$ with $n$ vertices, $m$ edges, without self-loops, a vertex $s\in V$, and an assignment $w:E\to \rrr$ of non-negative weights such that on input $(G,s,w)$, Dijkstra's algorithm requires $\Omega(n\log n +m)$ comparisons regardless of the implementation of the priority queue.

12.53   Note that this lower bound applies to the implementations of Dijkstra's algorithm. It does not mean that the single-source min-cost path problem with non-negative weights cannot be solved in a linear number of comparisons; this is an open problem.

12.59 ORD ($k$-way merge) (10 points)   Given $k$ sorted lists of data (real numbers), merge them into a single sorted list using comparisons. Your algorithm should cost $O(n\log k)$ (including bookkeeping) as $n\to\infty$, where $n$ denotes the total number of items on the $k$ lists combined (so in particular $n\ge k$), and comparison of real numbers and link update has unit cost. The number of comparisons should be $\lesssim cn\log_2 k$ for some constant $c$; state the smallest valid value of $c$ you can prove. For this second bound we assume $k\to \infty$.

Describe your algorithm in clean pseudocode. In the description you may refer to high level data structure commands implemented in class. Indicate why the algorithm will have the complexity (cost) stated.
Comment.   Copying real numbers can be replaced by link updates, so the only operation with real numbers that we need is comparison.

12.62 ORD (7 points) (Heapsort)   One can use a Heap to sort $n$ real numbers: first HEAPIFY the data, then EXTRACT-MIN until the heap becomes empty. Let $f(n)$ denote the number of comparisons this method uses. Show that $f(n) \lesssim cn\log_2 n$ for some constant $c$. State the smallest $c$ for which you can prove this bound.

12.66 BON (9 points)   We wish to sort $n$ real numbers given in a heap. (So the data have been preprocessed: they have been organized in a heap.) The data are real numbers; the operations we can do are comparison of reals and bookkeeping. Show that we still need $\gtrsim n\log_2 n$ comparisons.
WARNING. This is NOT an exercise about Heapsort. You have to show that every comparison-based sorting algorithm requires at least the stated number of comparisons -- the information encoded in the heap is not much help.

12.69 BON (12 points, due Feb 22)   Joe presents an algorithm that purports to sort lists of $n$ data using $o(n \log n)$ comparisons. Show that not even a 1% fraction of the data will be correctly sorted in the worst case (assuming the $o(n \log n)$ bound is true).
To rephrase, this means that for all sufficiently large values of $n$ there will be an input list of size $n$ such that no sublist of size $n/100$ will be properly sorted by Joe's algorithm.
Conceptual clarity is paramount (what exactly are you proving?). Elegance of the proof counts.
Clarification [02-22 16:50] As I hope should be clear from the first paragraph, the "sublists" mentioned in the second paragraph are not necessarily contiguous -- any $n/100$ entries from the list.

12.XX  

More to follow. Please check back later.

Material covered:   RELAX routine (updating costs and parent links in Dijkstra's algorithm). Dijsktra requires non-negative weights. Discussion of case of negative weights: negative cycles NP-hard. Correctness of Dijkstra's algorithm: relative loop invariants. HEAP implementation of Priority Queue -- please check updated slides (01-29 12:15pm).

11.XX  

11.XX  

More to follow. Please check back later.

Material covered:   (Free) trees, rooted trees. Rooted tree defined by parent links. BFS, BFS tree. Edge-weighted digraph, single source min-cost path problem. Priority queue data structure. Dijkstra's algorithm.

10.XX  

10.20 REVIEW   Breadth-First Search handout

10.25 STUDY   Dijkstra's algorithm handout

10.28 STUDY   the Analysis of Dijkstra's algorithm (proof of correctness) as described in the Loop invariants handout.

10.31 ORD (8 points)   Dijsktra's algorithm requires the weights to be non-negative. Give an example of a weighted rooted digraph $G$ and a vertex $v\in V(G)$ such that   (a)   $G$ is acyclic (has no directed cycles) and   (b)   all but one of the edges have non-negative weights and   (c)   Dijkstra's algorithm gives an incorrect value for the min weight path to $v$ from the root. Make your digraphs as small as you can. Show the parameters associated with each vertex (status, parent, current distance from root) after each round, initialization being "round zero."

10.34 DO/ORD (1+1+2+2+2 points)   (a) DO   "Loop invariants" Ex. 6.   (b) ORD   "Loop invariants" Ex. 10.

10.37 BON (5 points)   "Loop invariants" Ex. 7.

10.39 DO (really! this is the key to the correctness of Dijkstra's algorithm)   "Loop invariants" Ex. 8.

10.42 ORD (6 points)   "Loop invariants" Ex. 9.
Note that correctness includes the statement that a minimum weight path from $s$ to $v$ can be traced backwards along the parent links from $v$.
(This clarification was added on 02-03 at 21:15.)

10.49 ORD (7 points) (emergency exits):   We are given a weighted directed graph $G=(V,E,w)$ with nonnegative weights and a subset $S$ of the vertices (the "emergency exits"). From each vertex, find a min-cost path to the "nearest emergency exit" ("nearest" in terms of total weight of the path). These paths should form a forest (one tree for each vertex in $S$). (Represent the forest by parent links.) Prove that the cost of finding this forest is not greater than the cost of executing Dijkstra's algorithm on a weighted digraph slightly larger than $G$; state its number of vertices and edges.
Your solution should be very simple, just a few lines.

Material covered:   Digraph terminology. (Directed) path, (directed) walk. Accessibility. Accessibility transitive. Representation of digraph by array of linked lists. Token: name of a vertex (number in $[n]$). Unit cost model: operations with tokens at unit cost. APPEND, INSERT, DELETE. Enhancing a linked list: additional keys/links, doubly linked list. Linear-time conversion between array and linked list. Frame of single-pass algorithm. Single-source shortest path problem. Breadth-first search (BFS) data structure.

09.15 STUDY   the Class #7 material (updated Jan 24 at 13:30).

09.XX  

09.XX  

09.18 Convention   If $u,v$ are vertices in the digraph $G=(V,E)$, we write $u\to v$ to indicate that $(u,v)\in E$ and we say "$u$ is adjacent to $v$." When talking about paths, cycles, walks in a digraph, we mean directed paths, etc., unless expressly stated otherwise.

09.20 STUDY   Breadth-First Search (handout)

09.25 DO   Let $u,v$ be vertices of the digraph $G=(V,E)$. Assume there is a walk from $u$ to $v$ in $G$. Prove: there is a path from $u$ to $v$ in $G$.
Hint for an elegant proof: a shortest walk is always a path.

09.31 BON (10 points) (reducing walk to path)   Given a $u\to\dots\to v$ walk in a digraph $G$, find a $u\to\dots\to v$ path in $G$ in linear time.
Explanation.   Let $V=[n]$. Let $u=w_0,w_1,\dots,w_k=v$ be a walk (so $w_i\in V$ and $w_{i-1}\to w_i$ for all $i$ for which these statements make sense). Here is the computational task.

Input:   $V$ -- the list of vertices of $G$ and
    $W=[w_0,\dots,w_k]$, the list of vertices of the $u\to\dots\to v$ walk.
    (We are not given any representation of $G$.)
Output: a list $P=[p_0,\dots,p_{\ell}]$ that represents a $u\to\dots\to v$ path (so $p_i\in V$, $p_0=u, p_{\ell}=v$, $p_{i-1}\sim p_i$, and all the $p_i$ are distinct).

Target complexity: linear, i.e., $O(n+k)$, in the unit cost model.

Elegance counts in two ways:   (a)   simplicity and clarity of the algorithm   (b)   conceptual clarity and elegance of the proof of correctness.

09.55 CH   Prove:   $(\forall m\in\nnn)(\exists k\in\nnn)(m\mid F_k)$.

09.60 CH   Find an infinite sequence $(a_0, a_1, \dots)$ of non-negative integers such that $(\forall k,\ell\in\nnn_0)(a_k\mid a_{\ell} \iff k\mid \ell)$ but it is not true that $(\forall r,s\in\nnn_0)\left(\gcd(a_r,a_s) = a_{\gcd(r,s)}\right)$.

More to follow. Please check back later.

Material covered:   Graph theory terminology. Adjacency relation: irreflexive, symmetric. Neighbors. Degree. Isolated vertex. Subgraph. Cliques, cycles, paths. Walks. Equivalence relations. Accessibility: an equivalence relation; its equivalennce classes: connected components. Connected graph. Complement. Isomorphism. Distance.

Material covered:   Basic data structures: array, linked list. Counting sort. Radix sort. Graphs, digraphs. Representation by array of adjacency lists. Adjacency matrix.

07.15 Linked lists   Let $n\in \nnn$. Integers $i\in [n]$ will be referred to as tokens. They can be represented by binary strings of length $\lceil \log_2(n+1)\rceil$.
A linked list is a sequence of at most $n$ nodes. Each node has an address (a token) and contains a fixed number of keys (objects of any kind, e.g., real numbers) and a fixed number of tokens. Two such tokens are mandatory: the next link (the address of the next node on the list) and head link (the address where the list begins). If we are at the end of the list then the "next" link leads to "NIL" (indicator that the list has ended). A doubly linked list also has a "prev" link to the preceding node and a "tail" link, pointing to the end of the list.

07.20 Linked list instructions   We maintain the address of a "current node." At unit cost we can follow a link, updating the address of the current node. Further operations:

•   create$(L)$ -- creates an empty list $L$
•   update key in current node
•   update link in current node
•   ${\mathrm{APPEND}}(L,t)$ where $L$ is a list and $t$ is a key or list of keys; this ooperation adds a new node at the end of the list. The new node includes the list $t$ of keys and the required links
•   next-node (follow the "next" link, update "current node")
•   previous node
•   DELETE: delete current node. This is accomplished by updating a single link:   next(prev):=next(current), and updating the current node to prev
•   INSERT node before/after current node (update links)

07.XX  

07.XX  

07.XX  

07.40 DEF (representation of graphs/digraphs)   Let $G=(V,E)$ be a digraph, so $E\subseteq V\times V$ is a set of ordered pairs of vertices. If $(u,v)\in E$ then we say that $v$ is an out-neighbor of $u$ and $u$ is an in-neighbor of $v$. We write $N^+_G(u)$ to denote the set of out-neighbors of $u$ and $N^-(v)$ to denote the set of in-neighbors of $v$. The number of out-neighbors of $u$ is $\deg^+(u)=|N^+_G(u)|$, the out-degree of $u$, and the number of in-neighbors of $v$ is $\deg^-(v)=|N^-_G(v)|$, the in-degree of $v$.

We represent $G$ by an array of adjacency lists. The array lists the vertices (each vertex once), and entry $i$ in the array is the start of a linked list called $\Adj[i]$ which lists the out-neighbors of vertex $i$ (in any order, with repetitions permitted).

Example
  $1 \to 3 \to 4 \to 3\to NIL$
  $2 \to 1 \to 1 \to 4\to 2 \to 2\to NIL$
  $3 \to NIL$
  $4 \to 2 \to 3\to 1\to 3\to NIL$

So in this digraphs we have $N^+(1)=\{3,4\}$, $N^+(2)= \{1,2,4\}$, $N^+(3)=\emptyset$, $N^+(4)=\{1,2,3\}$.

The adjacency matrix of this digraph is $$ A_G = \begin{pmatrix} 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \end{pmatrix} $$ 07.43 (single pass)   Here is the frame of an algorithm that makes a single pass through the array of adjacency lists:

       for $i=1$ to $n$
             for $j\in\Adj[i]$
                    do something
             end(for)
       end(for)

07.46 pseudocode instructions for digraphs   Let $G$ be a digraph given in an adjacency list representation. When writing pseudocode, do not use commands or notation specific to programming languages; just use the for and while loop instructions and some basic list managment instructions (above).
You can also use Engish phrases in a pseudocode as long as they are unambiguous.

07.49 DEF (unit cost model)   We assume $V=[n]$. The vertices are tokens (bit-strings of length $\lceil n+1\rceil$). Operations on tokens include copying, viewing a token as an address (link) and following that link, adding/subtracting/comparing tokens, list operations (above). The cost of an operation on tokens is one unit.
"Running time" means the number of steps taken by an algorithm, where a "step" is a unit-cost token operation.

07.55 ORD (7 points) (reverse digraph)   Let $G$ be a digraph (directed graph). Let $G^{tr}$ denote the same digraph with all edges reversed. Assume $G$ is given in an adjacency list representation. Show that an adjacency list representation of $G^{tr}$ can be found in linear time, i.e., time $O(m+n)$, where $n$ is the number of vertices and $m$ is the total length of the adjacency lists. (So if the adjacency lists have no repeated entries then $m$ is the number of edges.) (The vertices are labeled $1,2,\dots,n$.)

Write a simple and elegant pseudocode. Elegance counts.
Hint   Make a single pass through the array of adjacency lists.

7.59 ORD (7 points) (monotone adjacency lists)   We call an adjacency list representation $A$ of a digraph monotone if for each vertex $i$, the list $A[i]$ is increasing: $A[i][1]\le A[i][2] \le \dots$ Given an adjacency list representation of a digraph $G$, create a monotone adjacency list representation of $G$ in linear time ($O(m+n)$). Your pseudocode should be very simple, just a few lines, with reference to pseudocodes constructed in prior work (in class or homework).

07.62 ORD (6 points) (repetition-free adjacency lists)   Given an adjacency list representation of a digraph $G$, get rid of repetitions in each adjacency list in linear time. So the output is an adjacency list representation of the same digraph where the adjacency lists have no repeated entries. Write a simple pseudocode.
Hint   Make a single pass through the array of adjacency lists.

07.65 DEF (strongly connected digraph)   A digraph is strongly connected if each vertex is accessible from each vertex.

07.68 ORD (7 points)   Given a digraph in an adjacency list representation, decide whether it is strongly connected, in linear time. Your pseudocode should be very simple, just a few lines, with reference to pseudocodes constructed in prior work (in class or homework).

07.XX  

07.XX  

07.XX  

07.XX  

07.XX  

More to follow. Please check back later.

Material covered:   Exponential growth. Fibonacci numbers. Dynamic programming: The Knapsack problem.

06.10 STUDY   "The Knapsack problem" handout

06.13 STUDY   Determinants   LinAlg Chapter 6

06.17 DEF (exponential growth)   We say that a function $f: \nnn\to\rrr$ grows at least exponentially if there exist $C > 1, c > 0$ such $f(n)= \Omega(C^{n^c})$.
We say that $f$ grows at most exponentially if there exist $C > 1, c > 0$ such $f(n)= O(C^{n^c})$.
We say that $f$ grows exponentially if it grows both at least and at most exponentially.
Example:   $f(n) = \eee^{\sqrt{n}} + (\sin n)\cdot n^{100}$ grows exponentially.
We say that $f(n)$ grows at least simply exponentially if there exists $C > 1$ such $f(n)= \Omega(C^{n})$.
We say that $f(n)$ grows at most simply exponentially if there exists $C > 1$ such $f(n)= O(C^{n})$.
We say that $f(n)$ grows simply exponentially if it grows both at least and at most simply exponentially.
Note.   Remember that the tower of exponentials notation $a^{b^c}$ (without parentheses) means $a^{(b^c)}$ and this is very different from $(a^b)^c = a^{bc}$.

06.19 DO   Show that $n!$ grows exponentially but not simply exponentially.

06.21 ORD (3 points)   Find a function $f(n)$ that grows simply exponentially but there is no $C$ such that $f(n) = \Theta(C^n)$. Give a very simple definition of your $f$.

06.23 DO   $(\forall C > 1)(n = o(C^n))$.
Hint.   Extend this statement to a real variable: $x = o(C^x)$ as $x\to\infty$. Use L'Hôpital's rule.

06.25 DO (exponential growth beats polynomial growth 1)   Prove: $(\forall D > 1)(\forall E)(x^E = o(D^x))$ as $x\to\infty$.
Do not use L'Hôpital's rule. Use 06.23 with a substitution of variables. (Bootstrapping: inferring a stronger statement from its weaker special case.)
Hint.   Let $C := D^{1/E}$.

06.27 ORD (4 points) (exponential growth beats polynomial growth 2)   Prove: $(\forall A > 1, c >0)(\forall B)(y^B = o(A^{y^c}))$ as $y\to\infty$. Give a very simple proof. Do not use L'Hôpital's rule. Use the preceding exercise with a substitution of variables (bootstrapping). Clearly state your substitution.
Example:   $y^{100} = o(1.001^{y^{0.001}})$.

06.30 Fibonacci numbers   The sequence $F_0, F_1, F_2,\dots$ is defined by the Fibonacci recurrence $$ F_k = F_{k-1} + F_{k-2} \qquad (k\ge 2) $$ and the initial values   $F_0 = 0$, $F_1=1$.
So the first few members of the sequence are $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline F_0 & F_1 & F_2 & F_3 & F_4 & F_5 & F_6 & F_7 & F_8 & F_9 & F_{10} & F_{11} & F_{12} \\ \hline 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 \\ \hline \end{array} $$ The members of this sequence are called Fibonacci numbers.

06.33 DO   Let   $A= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \,.$   Prove: for all $k\in\nnn$, $$A^k= \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix} \,.$$

06.36 DEF (Golden ratio)   The Golden ratio is the number $$ \phi = \frac{1+\sqrt{5}}{2} \approx 1.618034$$

06.37 DO   The Golden ratio is a root of the polynomial $x^2-x-1$. The other root is the algebraic conjugate of $\phi$, $$ \phibar = \frac{1-\sqrt{5}}{2} \approx - 0.618034$$ We have $\phi + \phibar = 1$, $\phi\cdot\phibar = -1$ and $\phi-\phibar =\sqrt{5}$.

06.39 DO   Prove: the golden ratio is equal to the ratio of a diagonal of a regular pentagon to a side of the pentagon.

06.40 FACT ("Binet's formula")   There is a closed-form expression for the Fibonacci numbers: $$ F_n = \frac{1}{\sqrt{5}}(\phi^n - \phibar^n) $$

06.42 DEF (nearest integer)   For $x\in\rrr$,   $\lfloor x \rceil$ denotes the integer nearest to $x$. Examples:   $\lfloor \pi \rceil = 3$ and $\lfloor -\pi \rceil = -3$. For numbers of the form $n+1/2$ $(n\in\zzz)$ the common convention is to take $\lfloor n+1/2 \rceil = n$, but this is an arbitrary choice and creates an infinite family of exceptions to the rule $\lfloor -x \rceil = -\lfloor x \rceil$.

06.45 DO   For all $n\in\nnn_0$, $$ F_n = \left\lfloor \frac{\phi^n}{\sqrt{5}} \right\rceil $$ It follows that $F_n \sim \phi^n/\sqrt{5}\,.$

06.48 BON/BON/DO (4+6 points, due Jan 30)   We say that the infinite sequence $(b_n\mid n\in\nnn_0)= (b_0,b_1,b_2,\dots)$ of real numbers is a Fibonacci-type sequence if it satisfies the Fibonacci recurrence (06.30). Prove:
  (a)   the geometric progression $(1,g,g^2,\dots)$ is a Fibonacci-type sequence if and only if $g\in\{\phi,\phibar\}$.
  (b)   the sequence $(b_n \mid n\in \nnn_0)$ is a Fibonacci-type sequence if and only if it is a linear combination of the two geometric progressions listed in (a), i.e., $$(\exists r,s\in\rrr)(\forall n\in\nnn_0)(b_n = r\phi^n + s{\phibar}^n).$$ Give a very simple proof. Do not use Binet's formula (06.40).
  (c) DO   Deduce Binet's formula (06.40) from part (b) above.

06.52 DEF (tiny parameters)   The unary representation of a positive integer $n$ is $111\dots 1$ ($n$ times). Example: $5 = 11111_{\text{unary}}$. We say that an input parameter to a computational task is tiny if it is given in unary.
Note that this increases the input size compared to our default representation of numbers (binary) and this can turn some exponential-time algorithms into polynomial-time.

06.54 ORD (3+3+5 points)   Let $b(m)$ denote the number of bits of the positive integer $m$.
  (a)   Find an asymptotic formula for $b(F_n)$ in the form $b(F_n) \sim cn$ for some constant $c > 0$. Determine the value of $c$.
  (b)   Infer from this that given $n$ (in binary), $F_n$ cannot be computed in polynomial time (in the bit model). Be specific about the quantities you are comparing.
  (c)   Show: if $n$ is tiny then $F_n$ can be computed in quadratic time. Describe your algorithm in simple pseudocode.

06.57 BON (7 points)   Given $k, m$ (in binary), compute $(F_k \bmod m)$ in polynomial time. (The output is always required in binary.) Describe your algorithm in elegant pseudocode.
The bit-length of your input is $n \sim \log k + \log m$. Prove an upper bound on the number of bit operations in the form of $O(n^c)$. State the smallest value of $c$ you can.

06.61 CH   Let $k,m \in \nnn_0$. Let $\gcd(k,m)=d$. Prove:   $\gcd(F_k,F_m)=F_d$. Only well structured, elegant proofs, please.

06.XX  

06.65 DEF   Let $x=(x_1,\dots,x_n)$ be a real vector $(x_i\in\rrr)$. The $\ell^1$-norm of $X$ is $\|x\|_1 := \sum_{i=1}^n |x_i|$.

06.68 ORD (7 points, due Jan 30)   Let $A$ be an $n\times n$ real matrix. Let $a_1,\dots, a_n$ denote the rows of $A$ (so $a_i\in\rrr^n$). Then   $$|\det(A)| \le \prod_{i=1}^n \|a_i\|_1\,.$$ To solve this problem, it is sufficient if you read LinAlg Sections 6.2 and 6.3.

06.71 CH   In the preceding exercise, assume all entries of $A$ are non-negative. Prove that equality holds if an only if either there is an all-zero row or there is exactly one non-zero entry in each row and each column.

06.74 ORD (7 points, due Jan 30)   Let $B_n = (b_{ij})$ denote the $n\times n$ matrix defined by $b_{ii}=1$ $(i=1,\dots, n)$, $b_{i,i+1}=1$ $(i=1,\dots, n-1)$, $b_{i,i-1}=-1$ $(i=2,\dots, n)$, and $b_{ij}=0$ everywhere else. For example, $$ B_5 = \begin{pmatrix} 1 & 1 & 0 & 0 & 0 \\ -1 & 1 & 1 & 0 & 0 \\ 0 &-1 & 1 & 1 & 0 \\ 0 & 0 &-1 & 1 & 1 \\ 0 & 0 & 0 &-1 & 1 \end{pmatrix} $$ Determine $\det(B_n)$. Your answer should be a very simple expression in terms of a familiar sequence.

06.79 BON (7 points)   Review the Knapsack problem. Assume all input variables are integers. Show that the algorithm presented in class and in the handout are NOT polynomial-time (in the bit model). Explicitly state what it is that one needs to prove to show that the algorithm is not polynomial-time. Conceptual clarity is paramount.
WARNING (added Jan 22, 11:10am)   Do not forget that we are doing worst-case analysis.

06.82 ORD (7 points)   Review the Knapsack problem. Assume all input variables are integers and all weights (including $W$) are tiny (see DEF 06.52). Show that the algorithm presented in class and in the handout is polynomial time. Let $N$ be the length of the input (including the unary representation of the weights and binary representation of the values). You need to show an upper bound of the form $O(N^c)$ on the number of bit operations. State the smallest $c$ you can prove.

06.85 BON (8 points)   Review the Knapsack problem. Consider the following variant.
The input is $w_1,\dots,w_n$ positive reals ("weights"), $v_1,\dots,v_n$ positive reals ("values"), and a non-negative real $V$ (target value). The goal is to achieve the target value at minimum weight: $$ \min_{I\subseteq [n]} \leftarrow \left\{\sum_{k\in I} w_k \,\bigg|\, \sum_{k\in I} v_k \ge V\right\}\,.$$ (If the target value is not achievable, i.e., $V > \sum_i v_i$, we say that the minimum weight is infinite.)
Prove: if all values are integers, including $V$ (while the weights are reals), the minium weight can be determined at $O(nV)$ cost, where an arithmetic operation (addition, subtraction) and comparison of two real numbers costs one unit, everything else (arithmetic on integers and bookkeeping) is free.

06.88 ORD (7 points, due Jan 30)   The all-ones square problem, stated in the handout titled "All-ones square: a dynamic programming example."

06.XX  

06.XX  

More to follow. Please check back later.

Material covered:   Modular exponentiation via repeated squaring. Proof of correctness using loop invariants.

05.15 STUDY   First two pages of the "Loop invariants" handout, up to and including Exercise 3.

05.20 STUDY   "Repeated squaring" handout

05.XX  

05.XX  

More to follow. Please check back later.

Material covered:   Decision trees. Information theory lower bound. Lower bound for comparison-based sorting. MERGE and MERGE-SORT algorithm. Analysis of these algorithms. The lower bound for comparison-based sorting is asymptotically tight. Amortized complexity.

04.10 REVIEW 03.15 and 03.18.

04.15 STUDY   the "Binary Search" handout

04.XX  

04.25 ORD (5 points) (sampling without replacement) Let $p$ be an odd prime and $2\le k \le p-1$. Let us pick a random subset $A\subseteq [p-1]$ of size $|A|=k$ uniformly from the $\binom{p-1}{k}$ such subsets. Prove: the probability that none of the elements of $A$ is a quadratic non-residue is less than $(1/2)^k$.

04.28 DO (ternary decision tree)   In a ternary decision tree, each query has 3 possible answers. Prove that to select an object out of $N$ possible objects, the decision tree must have depth $\ge \log_3 N$ (i.e., we need to ask at least $\log_3 N$ questions in the worst case to identify the selected object).

04.31 DO/Reward (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." All genuine coins have the same weight, and the fake coin has a different weight.) (b) REWARD PROBLEM Find an oblivious algorithm for this problem, i.e., specify your measurements (subsets of coins to put in each tray) in advance (your choice of which coins to put in each tray must not depend on the outcomes of previous measurements). Show that 3 measurements still suffice. (Do not hand in your solution. But do let me know if your proof of correctness is really elegant, not based on looking at several cases.)

04.34 ORD/BON (more than 12 coins)   Given $n$ coins, one of which is fake, we want to find the fake coin and also decide whether it is heavier or lighter, using measurements on a balance.
  (a) ORD (5 points)   Prove: if $n=14$ then 3 measurements do not suffice. Make your proof very simple.
  (b) BON (9 points)   Prove: if $n=13$ then 3 measurements do not suffice.
Solving (b) will NOT earn you the 5-point credit for (a). You need to give a very simple separate solution to (a).

04.38 BON (12 points, due Tue, Jan 23) (Evenly splitting the fake coins):   Suppose we have $2n$ coins, some of which are fake. All the fake coins have equal weight, and they are lighter than the genuine coins (which also have equal weight). Using $\sim \log_2 n$ measurements on a balance, divide the coins into two sets of $n$ coins of nearly equal weight. "Nearly equal" means if the number of fake coins is even, they must be evenly split between the two parts; if their number is odd, one part must have exactly one more fake coin than the other part. The number of measurements made must be asymptotically equal to $\log_2 n$.
Write your algorithm in elegant pseudocode.

04.42 ORD (4+6 points) (Find min)   Given $n$ real numbers, we want to determine their min in the comparison model. (Comparisons cost one unit each, bookkeeping is free.) Prove: (a) $n - 1$ comparisons suffice. Give a simple pseudocode. (b) $n - 2$ comparisons do not suffice.

04.45 BON (9 points) (Find min and max)   Given $n\ge 1$ real numbers, we want to determine both their min and their max in the comparison model. Prove: $\lfloor 3n/2\rfloor$ comparisons suffice.
(Note that this is rather surprising; how can determining the min reduce the cost of determining the max?)

04.55 ORD (5+5+5+8 points) (Strassen's matrix multiplication): If we multiply two $n\times n$ real matrices according to the textbook definition, we need to perform $n^3$ multiplications of real numbers and $n^2(n-1)=\Theta(n^3)$ additional additions of real numbers. In 1969, Volker Strassen found that this was not optimal: in analogy with Karatsuba's algorithm to multiply polynomials, Strassen reduced the multiplication of two $n\times n$ matrices to the multiplication of $7$ pairs of $n/2\times n/2$ matrices (as opposed to 8 pairs, which would be the obvious way, mimicking the textbook multiplication of $2\times 2$ matrices), plus a constant number of additions and subtractions of such matrices and some bookkeeping. The cost of the reduction is $O(n^2)$ (it involves a fixed number of additions and subtractions of $n/2 \times n/2$ matrices and some bookkeeping).
Here and below we assume $n$ is a power of $2$.
(a) First consider the model where we charge one unit cost for the multiplcation of two real numbers; addition, subtraction, and bookkeeping are free. Let $M(n)$ denote the cost of multiplying two $n\times n$ matrices in this model. Observe that, according to Strassen, $M(n)\le 7 M(n/2)$. Moreover, $M(1)=1$.   (a1)   Prove: $M(n)\le n^{\beta}$ where $\beta = \log_2 7 \approx 2.807$. Use direct calculation and induction; do not use the method of reverse inequalities. In particular, you cannot assume that the upper bound has the form $M(n)\le n^c$ for some $c$.   (a2)   Prove also that the inequality $M(n) < n^{\beta}$ does NOT follow for any value of $n = 2^k$ from the recurrence and the initial condition given. Clarify the LOGIC of this statement: state, what exactly needs to be shown.
(b1)   Now, factor in the cost of additions, subtractions, and bookkeeping. State the recurrent inequality for the complexity $T(n)$ under this cost model (number of arithmetic operations on real numbers and bookkeping).
(b2)   Prove that $T(n) = O(n^{\beta})$. Use the method of reverse inequalities.

04.61 ORD (5 points) (MERGE)   Let $A[1..m]$ and $B[1..n]$ be two sorted lists of real numbers: $A[1] \le A[2] \le \dots \le A[m]$ and $B[1] \le B[2] \le \dots \le B[n]$. Given these lists as inputs, create the merged list $C[1] \le C[2] \le \dots \le C[m+n]$. Do this using at most $m+n-1$ comparisons. (In this problem, the only thing we can do with real numbers is comparing them. All else is bookkeeping (recording the outcomes of the comparisons) and computation with integers $1,\dots,m+n-1$, all of which comes for free, we only count comparisons.) The comparisons we make should give us sufficient information to sort the combined list. Write a simple pseudocode.

04.64 BON (9 points, due Tue, Jan 23) (MERGE optimal)   Let $m=n$ in the preceding exercise. Prove that the algorithm of the preceding exercise is optimal in this case: $2n-2$ comparisons are not sufficient to create the merged list.
Warning: this is not about a particular method of merging; we are up against all conceivable methods. Conceptual clarity is paramount.

04.67 BON (8 points, due Tue, Jan 23) (MERGE not optimal)   Show that the two lists of Ex. 04.61 can be merged using $m\cdot \lceil\log_2(n+1)\rceil$ comparisons. Describe your algorithm in elegant pseudocode. Do not ignore rounding and do not ignore the possibility that some of the entries can be equal. You need to justify the exact upper bound claimed.
Note that if $m = o(n/\log_2 n)$ then this is much faster than the algorithm of Ex. 04.61.

04.XX  

04.XX  

04.XX  

More to follow. Please check back later.

Material covered:   Degree of polynomials. The Karatsuba algorithm to multiply polynomials. Divide-and-Conquer algorithms. Solving recurrent inequalities using the Method of Reverse Inequalities.

03.15 STUDY the handout "Divide and Conquer: the Karatsuba algorithm" (click "Handouts" on the banner)

03.18 STUDY the handout "Evaluation of recurrent inequalities: The method of reverse inequalities. The Fibonacci numbers."

03.XX  

03.XX  

More to follow. Please check back later.

Material covered:   Reviewed RYS communication protocol for Identity function. Proved upper bound on probability of error. Asymptotic notation.

02.15 STUDY the material posted below under Class 1. The exposition of some concepts is more detailed than was in class.

02.20 STUDY asymptotic notation   ASY (Asymptotic equality and inequality) Sections 1 (Sequences), 3 (limits), 4 (limsup, liminf), 5 (standard def of asymptotic equality), 6 (properties of asymptotic equality). DMmini Section 2.3 (little-oh, little-omega notation), 2.4 (big-Oh, big-Omega, big-Theta notation)

02.25 BON (9 points)   We are in 1.118, Case 5a. Bob confidently declares that "$X\neq Y$". We wish to find $i$ such that $X_i\neq Y_i$ (the $i$-th terms in the strings differ).
   Alice "knows" (has access to) $X$ (a binary string of length $N$) and a prime number $p < 2^k$
   Bob knows $Y$ (a binary string of length $N$) and $p$. Bob also knows $(X \bmod p)$.
   Devise a deterministic communication protocol that allows Alice and Bob to find $i$ as desired, with a small amount of communication.
   "Small" means $O(k^{c_1}(\log N)^{c_2})$ for some constants $c_1, c_2$. State the best constants you can get.

When solving problems from a handout such as ASY, you may use all lower-numbered problems from the same handout without proof.
Elegance counts. Complicated proofs lose points even if they are otherwise correct.

02.30 ORD (3+4 points)   ASY 6.5 (taking log of asymptotic equality)

02.33 ORD (5 points)   ASY 6.9(b) (asymptotics of $\ln(n!)$)

02.36 ORD (4+4 points)   DMmini 2.4.9 ($O(2^{b_n})$ vs $2^{O(b_n)}$)

02.42 BON (8 points, due Tue, Jan 16)   Let $p_n$ denote the $n$-th prime number. Infer from the Prime Number Theorem (ASY Thm 5.14) that $p_n \sim n\ln n$. (Actually this statement is equivalent to the PNT.)

02.45 CH   ASY 6.11 (log-asymptotics of product of primes)

02.48 BON (7 points, due Tue, Jan 16)   Prove:   $\nu^*(n) \sim \frac{\ln n}{\ln\ln n}$.   (See Notation 1.126) (Use the PNT)

02.XX  

02.XX  

More to follow. Please check back later.

Material covered:   Computational task. Model of computation. Cost. Worst-case analysis. Randmized algorithms. Communication complexity. Communication matrix. Mehlhorn--Schmidt Theorem (stated). Randomized communication. Communication complexity of equality.

01.20 Notation.   we write $\nnn=\{1,2,3,\dots\}$ for the set of natural numbers (positive integers) and $\nnn_0=\{0\}\cup \nnn$ for the set of non-negative integers. For $n\in\nnn_0$ we write $[n]=\{1,2,\dots,n\}$. So, for instance, $[3]=\{1,2,3\}$, $[1]=\{1\}$, and $[0]=\emptyset$.
$\zzz$ denotes the set of integers, $\rrr$ the set of real numbers, and $\ccc$ the set of complex numbers.

01.25 Computational task   Let $\In$ and $\Out$ denote two sets. The elements of $\In$ will be called inputs, the elements of $\Out$ outputs. Each input $x\in \In$ has an associated measure called size, denoted $\size(x)\in \nnn_0$.
A computational task is a function $f:\In\to \Out$ (or a relation $R\subseteq \In\times \Out$ if the input does not uniquely determine the output). In what follows, I am going to assume the task is a function, but the concepts can be extended to the case of relations.
Typically, $\In$ and $\Out$ consist of all finite strings over a given finite alphabet, e.g., all finite binary strings. In this case, the size is taken to be the length of the string. But in some models the input is a real vector $v=(v_1,\dots,v_k)$ ($v_i\in\rrr$) and the size of the input could be defined as $k$ (the dimension) or any of various norms of $v$.
Examples:   multiplication of integers written in binary (size: total number of input bits), multiplication of matrices with complex numbers as entries (size: the total number of matrix entries), sorting a list of real numbers (size: the length of the list), sorting a list of positive integers given in binary (size: total number of bits in the input), deciding whether a graph is 3-colorable (size: number of vertices plus number of edges of the graph), deciding whether a Boolean formula is satisfiable (size: number of occurrences of variables in the formula), deciding whether in a given positional game, a given position is a winning position for the next player (size: number of entries in a position, like "64" in chess if we ignore the castling and en passant rules). Examples when the task does not necessarily have a unique solution: find a 3-coloring of a given graph, find a satisfying assignment for a given Boolean formula, find a winning move for the next player.

01.28 Model of computation.   This concept is somewhat vague; we shall learn the meaning on a number of examples. A model of computation is a collection of "methods" that can be used to evaluate ("compute") certain functions $f$ ("solve" certain computational tasks). The key element of the model is the cost function.

01.31 Cost, resources.   Each "method" $M$, when applied to an input $x\in\In$, comes with its cost $c_M(x)$ which is a non-negative real number (most often, a non-negative integer).
The cost is usually defined as the amount of certain type of resource used, such as time (number of "elementary steps"), space (amount of memory used), depth (also called "parallel time": the number of rounds taken by a set of processors that work in parallel), number of multiplications of real or complex numbers, total number of arithmetic operations on real or complex numbers, number of queries to the input (think of the input as a database), amount of communication among processors, number of random bits used, etc.

01.34 Algorithm.   This concept will also remain somewhat vague and will be illustrated on numerous examples. An algorithm $\calA$ within a model of computation uses a particular method, allowed in the model, to evaluate the computational task $f$ on each input $x$. We denote the output produced by the algorithm $\calA$ by $\calA(x)$. The correctness of the algorithm means $$ (\forall x\in\In)(\calA(x)=f(x))\,$$ Proving correctness of the algorithm is the first task of the analysis of algorithms. The second task is to estimate the cost $c_{\calA}(x)$ of applying algorithm $\calA$ to input $x$, defined as $c_M(x)$ where $M$ is the methid used by the algorithm.

01.37 Worst-case analysis.   Our measure of the complexity of an algorithm is the maximum cost of the algorithm on the inputs of a given size: for $n\in\nnn_0$ we say that $$ C_{\calA}(n) = \max_{\size(x) \le n} c_{\calA}(x) $$ In other words, this is the cost of the worst input of a given size. (Each algorithm has its own worst inputs.)
The complexity of the computational task $f$ in the given model is a function $C(f,.): \nnn_0\to \rrr$ defined by $$ C(f,n) = \min_{\calA} C_{\calA}(n) $$ where the minimum is taken over all algorithms $\calA$ within the given model that solve the task $f$. In other words, $C(f,n)$ is the cost of the worst input of size $\le n$ for the best algorithm in the given model.
Our focus will be the asymptotic behavior of the function $C(f,.)$, i.e., the rate of growth of $C(f,n)$ for a given $f$ as $n\to\infty$.

01.40 Upper bounds on complexity.   Let $g: \nnn_0\to\rrr$ be a function.
To prove an upper bound $C(f,n) \le g(n)$, we need to exhibit an algorithm $\calA$ such that $(\forall n)(C_{\calA}(n) \le g(n))$. This means designing and analyzing a clever algorithm.

WARNING. The "worst input" is usually impossible to find. Arguments that say that a particular input is "clearly" the worst are usually incorrect.
So to prove something about the "worst input," we need to reason about all inputs. In order to prove that $C_{\calA}(n) \le g(n)$, we need to show that $$ (\forall x\in\In)(\size(x)\le n \Rightarrow c_{\calA}(x) \le g(n))$$

01.43 Lower bounds on complexity.   Let $h: \nnn_0\to\rrr$ be a function.
To prove a lower bound $C(f,n) \ge h(n)$ tends to be a much harder task: here we are up against all conceivable algorithms. What we need to prove is that for every algorithm $\calA$ that solves the computational task $f$, we have $C_{\calA}(n) \ge h(n)$. This means we need to analyze the computational model, usually an elusive task.

01.46 DO   The complexity of an algorithm is a non-decreasing function of $n$. The same is true for the complexity of a computational task.

01.49 Randomized algorithms   So far we have talked about deterministic algorithms (the input determines the output, and also the steps taken, if that makes sense in the given model). A randomized algorithm $\calB$ is a deterministic algorithm $\calA$ that in addition to the given input $x$ for $\calB$, also takes a random number $r$ and evaluates $\calA$ on input $(x,r)$. So the output $\calB(x)=\calA(x,r)$ is a random variable. In this case, instead of demanding that $\calB(x)=f(x)$, we are iterested in the probability of error, i.e., $$\Pr(\calB(x)\neq f(x))\,$$ where the probability refers to the choice of $r$ while $x$ is fixed. We want to keep this probability small. So the analysis of correctness of the algorithm (that it computes the target function $f$) is replaced by estimating the probability of error.
We can think of $r$ as a random $(0,1)$-string of a given length, or a random integer from the set $[k]$ for some $k\in\nnn$, or as a random real number from the $[0,1)$ interval. Random choice usually, but not always, refers to the uniform distribution. Sometimes we take a random number from the standard normal distribution.

01.55 DO   Let $m\in\nnn$. Let $b(m)$ denote the number of binary digits of $m$. Prove: $$ b(m) = 1+\lfloor \log_2 m \rfloor = \lceil \log_2(m+1) \rceil $$ Here $\lfloor x\rfloor$, the "floor" of the real number $x$, is the greatest integer $k$ such that $k\le x$. For instance, $\lfloor \pi\rfloor = 3$ and $\lfloor -\pi\rfloor = -4$.

01.58 STUDY the big-Oh notation   Read Section 2.4 of the DMmini lecture notes. Find the link in the preamble of this page (near the top).

01.61 DO   Let $b > 1$ and let $f:\nnn\to\rrr$ be a function. Show that the validity of the statement $f(n) = O((\log_b n)^2)$ does not depend on the base $b$ of the logarithm.

01.64 DEF (polynomial time)   Let $f:\nnn\to\nnn$ be a computational task. We measure the length of the input in its bit-length (number of digits in binary). Consider the bit-model: the cost is the number of bit operations (arithmetic, copying). We say that an algorithm in this model is a polynomial-time algorithm if the number of steps it takes in the bit-model is $O(n^C)$ for some constant $C$, where $n$ is the bit-length of the input. We say that the algorithm is linear-time if it takes $O(n)$ steps, and quadratic-time if it takes $O(n^2)$ steps. (Recall that the big-Oh notation always refers to an upper bound.)

In the following sequence of exercises, we shall always refer to the bit-model. In particular, all inputs will be given in binary.

01.66 DO   Show that the schoolbook algorithm   (a)   to add two integers is linear time, and   (b)   to multiply two integers is quadratic time.

01.68 ORD (6 points)   Prove that, given the input $x\in \nnn$, the power $3^x$ cannot be computed in polynomial time.

01.72 STUDY congruences   Read Sections 1 and 5 of the online handout "Euclid's algorithm and multiplicative inverse." (Click "Handouts" on the navigation bar at the top of this page.) These sections explain the congruence notation $a\equiv b\pmod m$.

01.75 DEF   Here and in the next sequence of exercises, let $p$ be an odd prime number (i.e., $p\neq 2$). We say that an integer $a$ is a quadratic nonresidue modulo $p$ if $(\forall k\in\zzz)(a\not\equiv k^2\pmod p)$.

01.78 DO   Prove: the number of quadratic nonresidues among the set $[p-1]$ is $(p-1)/2$.

In the next sequence of exercises, we shall consider the complexity of finding a quadratic nonresidue modulo a given prime $p$. This is a relational problem: the input ($p$) does not uniquely determine the output.

01.81 FACT   Given an integer $x$ and a prime number $p$, one can decide in polynomial time whether $x$ is a quadratic nonresidue modulo $p$.

01.83 Theorem (Nesmith Ankeny, 1951)   Let $n(p)$ denote the smallest quadratic nonresidue modulo $p$.
Under the Generalized Riemann Hypothesis (GRH), $n(p) = O((\log p)^2)$.
In other words, there exists a constant $C$ such that for all $p$ we have $n(p)\le C(\log p)^2$.
The Generalized Riemann Hypothesisis an unproven but widely believed mathematical statement. Even without the adjective "generalized," it is one of the greatest unsolved problems in mathematics.

01.85 ORD (5 points)   Design a very simple deterministic algorithm to find a quadratic nonresidue modulo the given odd prime number $p$. Describe your algorithm in pseudocode, meaning that you indicate the cycle structure (for or while loops) but otherwise describe your steps in English. Use a fact stated above. Do not prove that fact.
Prove that under the GRH, your algorithm runs in polynomial time. Describe your best complexity estimate in detail, and give the best exponent you can in the "polynomial time" statement. Your description of this "best exponent" should involve notation for the unspecified exponent implicit in the fact you use.
Remark. No polynomial-time algorithm for this task is known unconditionally, i.e., without making a strong mathematical assumption such as GRH.

01.88 ORD (7 points)   Design an extremely simple randomized polynomial-time algorithm that, given an odd prime $p$, finds, with probability at least $0.999,999$ (i.e., $1-10^{-6}$), a quadratic non-residue. Do not use any unproven assumptions. Again, use a fact stated above. Do not prove that fact.
Describe your best complexity estimate in detail, and give the best exponent you can in the "polynomial time" statement. Again, your description of this "best exponent" should involve notation for the unspecified exponent implicit in the fact you use.

01.95 Communication complexity (Andrew Chi-Chih Yao 1979: discrete model, a variation of a continuous model by Harold Abelson 1978)   In this model, two computing agent called Alice and Bob have access to $n$-bit strings $X$ and $Y$, respectively. Moreover, a function $f : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}$ is known to them in advance. Alice and Bob wish to collaboratively compute $f(X,Y)$. They each have unlimited computational power; any computation they perform has zero cost. However, they need to communicate with each other because each of them misses half the input, and they have to pay one unit for each bit communicated. So the cost is the number of bits communicated. The goal is for one of them to find the value $f(X,Y)$. They take turns communicating bit strings to the other. In advance they agree on a communication protocol (algorithm) that determines what bit-string each of them sends to the other on their turn; this bit-string is determined by the history of the communication and the input available to the communicating party. (This is similar to a bidding system in the card game of Bridge.)
We write $CC(f)$ to denote the communication complexity of the function $f$, i.e., the number of bits communicated under the best protocol for the worst input $(X,Y)$.

01.98 DO (trivial upper bound)   For any function $f : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}$ we have $CC(f) \le n$. This is achieved by the trivial protocol: Alice sends the entire string $X$ to Bob. Bob then has the entire input $(X,Y)$ and computes $f(X,Y)$ at no cost.

01.101 DEF   The communication matrix $M_f$ corresponding to the function $f : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}$ is the $2^n\times 2^n$ $(0,1)$-matrix (each entry is 0 or 1) whose rows and columns are labeled by the $(0,1)$-strings of length $n$ (there are $2^n$ such strings) and the entry corresponding to row $X$ and column $Y$ is $f(X,Y)$.

01.103 Theorem (Kurt Mehlhorn and Erik M. Schmidt, 1982) $$CC(f) \ge \log_2 \rank(M_f)$$

01.106 DO   Consider the task for Alice and Bob to decide whether $X=Y$ where $X,Y\in \{0,1\}^n$. We call this the identity function and denote it by $\id_n$: $$ \id_n(X,Y) = \begin{cases} 1 &\text{ if }\ X=Y \\ 0 &\text{ if }\ X\neq Y \end{cases} $$ Prove:   $CC(\id)=n$.
Proof.   The communication matrix $M_{\id_n}$ corresponding to this task is the $2^n\times 2^n$ identity matrix. The rank of this matrix is $2^n$, therefore $CC(\id)\ge \log_2 2^n = n$. On the other hand we know that $CC(f)\le n$ for all functions.     $\Box$

01.109 Notation (divisibility, remainder)
   1. Let $a,b\in \zzz$. We write $a\mid b$ if $(\exists x\in\zzz)(ax=b)$. In this case we say that $a$ divides $b$. Other verbal expressions of the same circumstance: $a$ is a divisor of $b$, $b$ is divisible by $a$, $b$ is a multiple of $a$.
   2. Let $a,m\in\zzz$ and $m\neq 0$. We write $(a \bmod m)$ to denote the unique non-negative integer $r$ such that $0\le r\le |m|-1$ and $a-r$ is divisible by $m$. So $r$ is the smallest non-negative remainder of $a$ divided by $m$. (We also say $r$ is "$a$ modulo $m$".)
Examples:   $(24 \bmod 7)=3$ because $7\mid 24-3=21$.
Also, $(24 \bmod -7)=3$ because $-7\mid 24-3=21$.
Show that $(-24 \bmod 7)=4$.

01.112 DO   (a)   Zero is divisible by every integer, including by zero: $0\mid 0$. Why does this statement not violate the prohibition of division by zero?
  (b)   Prove that $0$ is the only integer divisible by all integers.   (c)   Find all integers $x$ such that $(\forall b\in\zzz)(x\mid b)$

01.115 DO (remainder vs. congruence)    Let $a,b,m\in\zzz$ and $m\neq 0$.
  (a)   Prove:   $r = (a\bmod m)$ if and only if $r$ is the smallest non-negative integer such that $a\equiv r\pmod m$ ($a$ is congruent to $r$ modulo $m$). (See 01.72 for the congruence notation).
  (b)   Prove:   $(a \bmod m)=(b \bmod m)$ if and only if $a\equiv b \pmod m$.

01.118 (An efficient randomized protocol: Rabin-Yao-Simon cca. 1980)
The protocol has two parameters, $n$ (the length of the input strings $X,Y$) and $k$, related to the number of bits to be communicated, $2\le k \le n$. Typically, $k$ will be much smaller than $n$.

   1. Alice generates a random prime number $p < 2^k$ represented in binary as a $k$-bit $(0,1)$-string (leading zeros permitted)
   2. Alice computes $(X \bmod p)$, again represented in binary as a $k$-bit $(0,1)$-string.
   3. Alice $\to$ Bob:   $p$, $(X\bmod p)$       ($2k$ bits of communication)
   4. Bob computes $(Y \bmod p)$.
   5a. If $(X \bmod p)\neq (Y \bmod p)$ then Bob declares "$X\neq Y$"
   5b. Else, Bob declares "$X = Y$".

01.121   In case 5a, Bob cannot be wrong (0 probability of error). However, if case 5b, Bob can be wrong. We need to estimate the probability of error; we need to show that for surprisingly small values of $k$, the propbability of error will be negligible.

01.124 Notation (prime counting function)   For $x\in\rrr$, the value $\pi(x)$ is defined as the number of prime numbers $\le x$.
Examples:   $\pi(10)=4$, $\pi(100)=25$ (check!), $\pi(\pi)=2$, if $x < 2$ then $\pi(x)=0$.

01.126 Notation (number of prime divisors)   For $m\in\nnn$, let $\mu(m)$ denote the total number of primes of which $m$ is the product (the same prime may be counted multiple times), and $\nu(m)$ the number of distinct prime divisors of $m$.
Let $\mu^*(m) = \max\{\mu(k)\mid k\in [m]\}$ and $\nu^*(m) = \max\{\nu(k)\mid k\in [m]\}$.
Examples:   $\mu(8)=3$, $\nu(8)=1$, $\mu(72)=5$, $\nu(72)=2$
$\mu^*(8)=3$, $\nu^*(8)=2$, $\mu^*(72)=6$, $\nu^*(72)=3$ (check!)

01.127 ORD (4 points)   Determine $\mu^*(2^n)$.

01.128 BON (4 points)   Determine $\nu^*(10^4)$. Show all your work. Do as little calculation as possible. (As always, prove your answer.)

01.131 DO+ORD Let $m\in\nnn.$   (a)   DO $\nu(m)\le \mu(m)$. Infinitely often $\nu(m)=\mu(m)$.   (b)   ORD (3 points)   $\mu(m) \le \log_2(m)$.

01.134 DO (probability of error)   Let $X\neq Y$. Then $$ \Pr(\text{error})=\frac{\text{number of distinct primes $p \le 2^k$ dividing }X-Y}{\pi(2^k)} \le \frac{\nu(X-Y)}{\pi(2^k)} \le \frac{\nu^*(2^n)}{\pi(2^k)} \le \frac{\mu^*(2^n)}{\pi(2^k)} = \frac{n}{\pi(2^k)} $$

01.XX  

01.XX  

More to follow. Please check back later.