AS ALGO 3

Problem 1

Part a

For $0⩽i⩽m$ and $0⩽j⩽n$, define

$$\begin{array}{r}DP[i][j]=\text{shortest common supersequence of }A[\mathrm{1..}i]\text{ and }B[\mathrm{1..}j],\end{array}$$

where substrings defined by invalid ranges are considered to be the empty string.

The natural recurrence is

$$\begin{array}{rl}& DP[i][j]=\{\begin{array}{ll}i& j=0\\ j& i=0\\ DP[i-1][j-1]+1& A[i]=B[j],i\ne 0,j\ne 0\\ 1+\min \{DP[i][j-1],DP[i-1][j]\}& \text{otherwise}.\end{array}\end{array}$$

Proof.

The cases for $i=0$ and $j=0$ are clear. Suppose $S$ is the SCS of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$. Suppose $S$ has length $l$. If $A[i]=B[j]=:c$, then $S[l]$ must be $c$. $S[\mathrm{1..}l-1]$ must be the SCS of $A[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j-1]$; if it weren’t, we would be able to construct a shorter common subsequence of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$ by the usual cut-and-paste argument. Thus, $DP[i][j]=DP[i-1][j-1]+1$. If $A[i]\ne B[j]$, then $S[l]$ must be either $A[i]$ or $B[j]$, and the same argument yields either $S[\mathrm{1..}l-1]$ is the SCS of $A[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j]$ or the SCS of $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j-1]$ respectively.□

$$\begin{array}{rl}& \text{SCS}(A[\mathrm{1..}m],B[\mathrm{1..}n]):\\ & DP\leftarrow \text{newArray}(m,n)\\ & \text{for }i\in [\mathrm{0..}m]:\\ & \text{for }j\in [\mathrm{0..}n]:\\ & \text{if }i=0:DP[i][j]\leftarrow j\\ & \text{else if }j=0:DP[i][j]\leftarrow i\\ & \text{else if }A[i]==B[j]:DP[i][j]\leftarrow DP[i-1][j-1]+1\\ & \text{else }DP[i][j]\leftarrow 1+\min \{DP[i][j-1],DP[i-1][j]\}\\ & \text{return }DP[m,n]\end{array}$$

The algorithm runs in $O(mn)$ time.

Part b

The problem of finding the longest bitonic subsequence $(\text{LBS})$ can be reduced to the problem of finding the longest increasing subsequence $(\text{LIS})$:

$$\text{LBS}(X[\mathrm{1..}n])=\underset{2⩽i⩽n-2}{\max }\{\text{LIS}(X[\mathrm{1..}i])+\text{LIS}(\text{reverse}(X[i+\mathrm{1..}n]))\}.$$

Below, we implement an algorithm for $\text{LIS}$ which runs in $O(n\log n)$ time.

$\text{pos}(B,a)$ returns the largest index $i$ of $B$ such that $B[i]<a$.

$$\begin{array}{rl}& \text{LIS}(A[\mathrm{1..}m]):\\ & B\leftarrow []\\ & \text{for }a\in A[\mathrm{1..}m]:\\ & p\leftarrow \text{pos}(B,a)\\ & \text{if }p==B.\text{length}:B.\text{append}(a)\\ & \text{else }:B[p+1]\leftarrow a\\ & \text{return }B.\text{length}\end{array}$$

Claim 336.1(Claim).

In the course of its execution, if the algorithm places $A[i]$ in position $b$ of $B$, there exists an increasing subsequence of $A[\mathrm{1..}i]$ of length $b$ ending in $A[i]$.

Proof.

his is clear for$b=1$. Suppose the claim is true for $b>1$. Suppose the algorithm places $A[i]$ in position $b+1$. There exists $k<i$ such that $A[k]<A[i]$ and the algorithm placed $A[k]$ in position $b$. By the induction hypothesis, there exists an increasing subsequence of length $b$ ending in $A[k]$; appending $A[i]$ gives one of length $b+1$.□

It is also clear that if $A[i_1],A[i_2],\dots ,A[i_k]$ is any increasing subsequence of $A$, the length of $B$ at the end of execution will be greater than or equal to $k$. Thus, it follows that $B.\text{length}$ is the length of the longest common subsequence.

This allows $\text{LBS}$ to run in $O(n^2\log n)$ time.

$$\begin{array}{rl}& \text{LBS}(X[\mathrm{1..}n]):\\ & A,B\leftarrow []\\ & \text{for }i\in [\mathrm{2..}n-2]\\ & A[i]\leftarrow \text{LIS}(X[\mathrm{1..}i])\\ & B[i]\leftarrow \text{LIS}([n-i+\mathrm{1..}n])\\ & ans\leftarrow 0\\ & \text{for }i\in [2,n-2]:ans\leftarrow \text{max}(ans,A[i],B[n-i])\\ & \text{return }ans\end{array}$$

Part c

$$\begin{array}{rl}& \text{LOS}(X[\mathrm{1..}n]):\\ & up,down\leftarrow 1\\ & \text{for }i\in [\mathrm{2..}n]:\\ & \text{if }X[i]>X[i-1]:up\leftarrow down+1\\ & \text{if }X[i]<X[i-1]:down\leftarrow up+1\\ & \\ & \text{return }\max (up,down)\end{array}$$

It is clear that there exists an alternating subsequence of $X[\mathrm{1..}n]$ of length $\text{LOS}(X[\mathrm{1..}n])$. Since $\text{LOS}$ counts the number of oscillations, a longer oscillating subsequence cannot exist. The algorithm runs in $O(n)$ time.

Part d

A sequence $(X_{i_1},X_{i_2},\dots ,X_{i_k})$ is convex iff its consecutive differences are strictly increasing:  

$${\Delta }_t:=X_{i_{t+1}}-X_{i_t}\text{and}{\Delta }_1<{\Delta }_2<\cdots <{\Delta }_{k-1}.$$

So we must find the longest subsequence of indices whose consecutive differences are strictly increasing.

Define $D[a][b]=X[b]-X[a]$ for $(a<b)$ and $D[a][a]=-\infty$. Let  

$$\text{DP}[a][b]=\text{length of the longest convex subsequence whose last two indices are }a<b.$$

Then the natural recurrence is

$$\begin{array}{rlr}& \text{DP}[a][a]=1& \text{(base)}\\ & & \\ & \text{DP}[a][b]=1+\underset{k⩽a,D[k][a]<D[a][b]}{\max }\text{DP}[k][a]& (a<b)\end{array}$$E1

The algorithm

$\text{zip}$ accepts two arrays $A$ and $B$ of size $n$ and returns an array $C$ of size $n$ such that $C[i]=(A[i],B[i])$. $\text{SortBySlot2}$ accepts the output of $\text{zip}$ and sorts it such that the values in the second slot are increasing. $\text{pos}(F,c)$ returns the maximum index $i$ in $F$ such that $F[i][1]<c$ using binary search.

$$\begin{array}{rl}& \text{ConvSubseq}(X[\mathrm{1..}n]):\\ & D\leftarrow \text{newArray}(n,n)\\ & \\ & \text{for }i\in [\mathrm{1..}n-1]:\\ & \text{for }j\in [i+\mathrm{1..}n]:\\ & D[i,j]\leftarrow X[j]-X[i]\\ & \\ & \text{for }i\in [\mathrm{1..}n]:D[i,i]\leftarrow -\infty \\ & \\ & DP\leftarrow \text{newArray}(n,n)\\ & \text{for }i\in [\mathrm{1..}n]:DP[i,i]\leftarrow 1\\ & \text{for }i\in [\mathrm{1..}n-1]:\\ & F\leftarrow \text{SortBySlot2}(\text{zip}(DP[\mathrm{1..}i,i],D[\mathrm{1..}i,i]))\\ & \text{for }j\in [\mathrm{2..}i]:F[j][0]\leftarrow \text{max}(F[j][0],F[j-1][0])\\ & \text{for }j\in [i+1,n]:DP[i][j]\leftarrow F[\text{pos}(F,D[i][j])][0]+1\\ & \\ & \text{return }\text{max}(DP)\end{array}$$

Correctness

Claim 336.2(Claim).

After the outer loop has processed all indices $(a^{\prime }\le a)$, for every $(k\le a)$ the table entry $(DP[k,a])$ equals the length of the longest convex subsequence whose last two indices are $(k<a)$ (Also $(DP[a,a]=1)$).

We initialize $(DP[1,1]=1)$. The inner loop for $a=1$ constructs $DP[1,j]$ for $j>1$. The list $F$ contains only the sentinel pair $(1,-\infty )$, so pos(F, D[1,j]) picks that sentinel and sets $DP[1,j]=1+1=2$, which is correct.

Inductive step. Suppose the invariant holds for all $a^{\prime }<a$. Consider fixed $a$. We form the list $F$ of pairs $(DP[k,a],D[k,a])$ for $k=1,\dots ,a$ (including the sentinel $k=a$ with $DP(a,a)=1$ and $DP[a,a]=-\infty$). We sort $F$ in increasing order of the second slot, and take prefix maxima over the first slot, that is, we set $F[i][0]$ to be ${\max }_{1⩽j⩽i}F[j][0]$. Thus pos(F, D[a,b]) finds the maximal $DP[k,a]$ among indices $k<a$ with $D[k,a]<D[a,b]$. The assignment

$$DP[a][b]=F[\text{pos}(F,D[a][b])][0]+1$$

for each $b>a$ exactly implements the recurrence in (E1). Therefore after processing index $a$, the invariant holds for all pairs ending at $a$.

Complexity

• Precomputing differences: $O(n^2)$.
• For each $a\in [\mathrm{1..}n]$ we sort $a$ pairs in $O(a\log a)$, totaling $O(n^2\log n)$.
• For each $a$ we then answer $n-a$ queries pos by binary search on $F$, with an overall complexity of $O(n^2\log n)$.

Thus, the algorithm runs in $O(n^2\log n)$.

---

Problem 2

Let P be a set of n points evenly distributed on the unit circle, and let S be a set of m line segments with endpoints in P. The endpoints of the m segments are not necessarily distinct; n could be significantly smaller than 2m. (a) Describe an algorithm to find the size of the largest subset of segments in S such that every pair is disjoint. Two segments are disjoint if they do not intersect even at their endpoints. (b) Describe an algorithm to find the size of the largest subset of segments in S such that every pair is interior-disjoint. Two segments are interior-disjoint if their intersection is either empty or an endpoint of both segments. (c) Describe an algorithm to find the size of the largest subset of segments in S such that every pair intersects. (d) Describe an algorithm to find the size of the largest subset of segments in S such that every pair crosses. Two segments cross if they intersect but not at their endpoints.

Let $P=[\mathrm{1..}n]$ be the list of points and $S[\mathrm{1..}m]$ be the list of edges. Represent edges by objects with properties $\text{left}$, $\text{right}$, and $\text{id}$, where $e.\text{left},e.\text{right}\in P$, $e.\text{left}<e.\text{right}$, and $e.\text{id}\in [\mathrm{1..}m]$ for all edges $e\in S$.

Part a

Define

$$\begin{array}{r}DP[i][j]=\text{largest independent set of edges in }S\text{ with both end points in }[i..j]\end{array}$$

for $1⩽i<j⩽n$, with $DP[i][i]=0$.

The recurrence is (any out of bounds access returns 0)

$$\begin{array}{rl}& \\ DP[i][j]& =0(j⩽i)\\ DP[i][j]& =\max \left\{DP[i][j-1],1+\underset{e\in S,e.\text{right}=j,i⩽e.\text{left}⩽j-1}{\max }DP[i,e.\text{left}-1]+DP[e.\text{left}+1,j-1]\right\}.\end{array}$$

The edges are preprocessed to obtain a list $E$, where $E[j]$ is a list of all edges with $e.\text{right}=j$. This can be done in $O(m)$ time.

$$\begin{array}{rlr}& \text{MaxIndSet}(P,S,E):& \\ & DP\leftarrow \text{newArray}(n,n)& \\ & DP[i][j]\leftarrow 0\text{ for }j⩽i& \\ & \text{for }l\in [\mathrm{1..}n-1]:& \\ & \text{for }i\in [\mathrm{1..}n-l]:& \\ & j\leftarrow i+l& \\ & ans\leftarrow DP[i][j-1]& \\ & \text{for }e\in E[j]:\text{if }i⩽e.\text{left}⩽j-1:& (\ast )\\ & ans\leftarrow \text{max}(ans,1+DP[i,e.\text{left}-1]+DP[e.\text{left}+1,j-1])& \\ & DP[i][j]\leftarrow ans& \\ & & \\ & \text{return }DP[1][n]& \end{array}$$

Edge $e$ is accessed for the computation of $DP[i][j]$ with $e.\text{right}=j$. Thus, the for loop $(\ast )$ takes $O(mn)$ time overall. Filling in the DP array takes $O(n^2)$ time, so the total running time is $O(n^2)+O(mn)=O(mn)$.

Part b

We only need to slightly modify the definitions from part a. Let $E[i][j]$ be $1$ if there exists an edge with $e.\text{left}=i$ and $e.\text{right}=j$, and $0$ otherwise.

$$\begin{array}{rl}& \\ DP[i][j]& =0(j⩽i)\\ DP[i][j]& =E[i][j]+\max \left\{DP[i][j-1],\underset{e\in S,e.\text{right}=j,i+1⩽e.\text{left}⩽j-1}{\max }DP[i,e.\text{left}]+DP[e.\text{left},j]\right\}.\end{array}$$

The algorithm is essentially the same as in part a, and runs in $O(mn)$ time.

Part d

Let $E[\mathrm{1..}n-1]$ be a 2d array such that $E[i]$ is an array containing all edges $e$ such that $e.\text{left}=i$ sorted in decreasing order of the property $\text{right}$. Assign $e.\text{id}$ to be the index of $e$ in $\text{flatten}(E)$ for all $e\in S$.

Let $N[\mathrm{1..}n-1]$ be an array such that $N[i]$ is the number of edges $e$ satisfying $e.\text{left}⩽i$.

Let $F[\mathrm{2..}n]$ be a 2d array such that $F[i]$ is an array containing all edges $e$ such that $e.\text{right}=i$ sorted in decreasing order of the property $\text{left}$.

$$\begin{array}{rl}& \text{MaximumClique}(N,F):\\ & ans\leftarrow 0\\ & \text{for }i\text{ in }[\mathrm{1..}n-1]:\\ & ans=\text{max}(ans,\text{LIS}(\text{map}(e\to e.\text{id},\text{filter}(e\to e.\text{id}⩽N[i],\text{flatten}(F[i+\mathrm{1..}n])))))\\ & \text{return }ans\end{array}$$

The preprocessing requires $O(m\log m)$ time. $\text{MaximumClique}(N,F)$ runs in $O(mn\log m)$ time.

Correctness

We wish to encode the information provided about the circle as an enumeration $e_1,\dots ,e_m$ of the edges and a string $s$ over the alphabet $\{{⊢}_i,{⊣}_i:i\in [\mathrm{1..}m]\}$ such that

1. Each symbol in the alphabet appears exactly once, and ${⊢}_i$ appears before ${⊣}_i$.
2. $e_i$ and $e_j$ with $e_i.\text{left}⩽e_j.\text{left}$ intersect(interiors intersect, no shared endpoints) iff ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ is a subsequence of $s$
3. $e_i.\text{left}<e_j.\text{left}$ iff ${⊢}_i$ appears before ${⊢}_j$ in $s$
4. $e_i.\text{right}<e_j.\text{right}$ iff ${⊣}_i$ appears before ${⊣}_j$ in $s$.

Let the enumeration be given by the $\text{id}$ property of the edges assigned above. Construct $s$ like so:

$$\begin{array}{rl}& T\leftarrow []\\ & \text{for }i\in [\mathrm{1..}n]:\\ & temp\leftarrow \text{""}\\ & \text{for }e\in F[i]:temp.\text{append}(\text{’}{⊣}_{e.\text{id}}\text{’})\\ & \text{for }e\in E[i]:temp.\text{append}(\text{’}{⊢}_{e.\text{id}}\text{’})\\ & T.\text{append}(temp)\\ & \\ & s\leftarrow \text{flatten}(T[\mathrm{1..}n])\end{array}$$

Suppose $e_i,e_j\in S$, $e_i.\text{id}=i$, $e_j.\text{id}=j$ $e_i.\text{left}⩽e_j.\text{left}$.

1. Suppose $e_i$ and $e_j$ intersect in the interior of the circle. We must have $e_i.\text{left}<e_j.\text{left}$. By the manner in which we assigned the $\text{id}$ property, $i<j$. Also, $e_i.\text{right}<e_j.\text{right}$. Therefore, ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ is a subsequence of $s$.
2. Suppose $e_i$ and $e_j$ do not intersect, even at their endpoints. Then, we have $e_i.\text{left}<e_j.\text{left}$ and $e_i.\text{right}>e_j.\text{right}$. It follows that ${⊢}_i{⊢}_j{⊣}_j{⊣}_i$, is a subsequence of $s$, and since each symbol appears only once, ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ cannot be a subsequence of $s$.
3. Suppose $e_i.\text{left}=e_j.\text{left}$ and $e_i.\text{right}>e_j.\text{right}$. Since every slot of $E$ is sorted in decreasing order of the property $\text{right}$, $j>i$. It follows that ${⊢}_i{⊢}_j{⊣}_j{⊣}_i$ is a subsequence of $s$, and thus ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ cannot be a subsequence of $s$.
4. Suppose $e_i.\text{right}=e_j.\text{right}$ and $e_i.\text{left}<e_j.\text{left}$. Again, $i<j$. Since each slot of $F$ is sorted in decreasing order of the property $\text{left}$, it follows that ${⊢}_i{⊢}_j{⊣}_j{⊣}_i$ is a subsequence of $s$, and thus ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ cannot be a subsequence of $s$.

We have shown that ${⊢}_i{⊢}_j{⊣}_i{⊣}_j$ is a subsequence of $s$ $⟺$ $e_i$ and $e_j$ intersect in the interior of the circle. Since $s$ is constructed in such a way that the ${⊢}_k$‘s appear in increasing order of the edge $\text{id}$s, it. suffices to find the longest increasing subsequence of ${⊣}_k$‘s in tails $\text{flatten}(S[i..n])$ such that $e_k.\text{left}<i$. This is exactly what $\text{MaximumClique}$ does.

Part c

We need only make a few changes to the solution of part d.

Let $E[\mathrm{1..}n-1]$ be a 2d array such that $E[i]$ is an array containing all edges $e$ such that $e.\text{left}=i$ sorted in increasing order of the property $\text{right}$. Assign $e.\text{id}$ to be the index of $e$ in $\text{flatten}(E)$ for all $e\in S$.

Let $N[\mathrm{1..}n-1]$ be an array such that $N[i]$ is the number of edges $e$ satisfying $e.\text{left}⩽i$.

Let $F[\mathrm{2..}n]$ be a 2d array such that $F[i]$ is an array containing all edges $e$ such that $e.\text{right}=i$ sorted in increasing order of the property $\text{left}$.

This makes $\text{MaximumClique}$ recognize edges which share an endpoint as intersecting vertices.

Now, $\text{MaximumClique}(N,F)$ returns the required result in $O(mn\log m)$ time.

---

Problem 3

We can assume all sequences start with $\text{DBL}$. Note that no shortest sequence will have two consecutive increments, since $\text{DBL}\to \text{INC}\to \text{INC}$ can be replaced by $\text{INC}\to \text{DBL}$. Thus, if a shortest sequence has $d$ doublings, it can have at most $d$ increments. Such sequences of $\text{DBL}$ and $\text{INC}$ can be interpreted as binary numbers, which the following algorithm exploits:

$$\begin{array}{rl}& \text{OptSeq}(n):\\ & B\leftarrow \text{binary representation of }n,\text{with }B[1]\text{ being the MSB}\\ & steps\leftarrow 0,num\leftarrow 1\\ & \text{for }i\in [\mathrm{2..}B.\text{length}]:\\ & \text{if }B[i]==1:num\leftarrow 2\ast num+1;steps\leftarrow steps+2\\ & \text{if }B[i]==0:num\leftarrow 2\ast num;steps\leftarrow steps+1\\ & \text{return }steps\end{array}$$

Let $\lambda (n)$ denote the length of the shortest sequence of increments and doublings which achieves from $1$. It is evident that the algorithm follows a sequence of increments and doubles, and that $num=n$ after the conclusion of the for loop. Thus, $\text{OptSeq}(n)$ is an upper bound for $\lambda (n)$. Suppose the sequence $S_1$ discovered by $\text{OptSeq}$ uses $d_1$ doublings and $i_1$ increments. Then, $n⩾2^{d_1}+i_1$. Suppose $S_2$ is the shortest possible sequence, achieving $n$ with $d_2$ doublings and $i_2$ increments. Suppose $d_2<d_1$. Since $i_2\le d_2$ and no two increments can appear consecutively, we have $n⩽2^{d_2+1}-1<2^{d_1}$, a contradiction. If $i_2<i_1$, we would have and equality of the form

$$2^{{\alpha }_1}+2^{{\alpha }_2}+\cdots +2^{{\alpha }_{i_2}}=2^{{\beta }_1}+2^{{\beta }_2}+\cdots +2^{{\beta }_{i_1}},$$

with ${\alpha }_1<{\alpha }_1<\cdots <{\alpha }_{i_2}$, ${\beta }_1<{\beta }_2<\cdots <{\beta }_{i_1}$, and $i_2<i_1$, which is impossible. This, $\text{OptSeq}(n)$ is optimal.

---

Problem 4

Part a

Let $S=\{v_1,\dots ,v_n\}$ be the columns of $T$. Let $M$ denote the tuple $(S,\mathcal{I})$. Clearly $\varnothing \in \mathcal{I}$. If $A\in \mathcal{I}$ and $B\subset A$ then any linear combination of vectors in $B$ may be viewed as if it were in $A$, hence $B$ is linearly independent, i.e. $B\in \mathcal{I}$. Further, if $A,B\in \mathcal{I}$ with $|A|>|B|$ then $A⊈\text{span }B$, since if that were the case, $\text{span }A$ would be spanned by fewer than or equal to $|B|$ vectors, contradicting the independence of $A$. Let $x\in A\setminus \text{span }B$. Indeed $B\cup \{x\}\in \mathcal{I}$ since $x\notin \text{span }B$ and $B$ is linearly independent. Hence $M$ is a matroid.

Part b

Let $M=(S,\mathcal{I})$ and let $M^{\prime }=(S,{\mathcal{I}}^{\prime })$. Clearly $\varnothing \in {\mathcal{I}}^{\prime }$ since ${\varnothing }^c=S$ must contain some maximal independent set of $M$. If $A\in {\mathcal{I}}^{\prime }$ and $B\subset A$ then $A^c\subset B^c$ and since $A^c$ contains a maximal independent set of $M$, so does $B^c$ and hence $B\in {\mathcal{I}}^{\prime }$.

Suppose $A,B\in {\mathcal{I}}^{\prime }$, and $|A|>|B|$. For all $a\in A$, suppose $B\cup \{a\}\notin {\mathcal{I}}^{\prime }$, that is, $(B\cup \{a\}{)}^c$ does not contain a maximal independent set of $M$. It follows that every maximal independent set of $M$ in $B^c$ contains $A$. Since $A\in {\mathcal{I}}^{\prime }$, $A^c$ must contain a maximal independent set $C$ of $M$. Since $C$ does not contain $A$, $C$ cannot lie in $B^c$, so $C$ must intersect $B$. However, by using the exchange property of $M$, every element $b\in B\cap C$ can be replaced with an element $a\in D$, where $D$ is an independent set in $B^c$. Let $E$ be the set obtained from $C$ after all elements of $C\cap B$ have been replaced with elements of $D$. Since all maximal independent sets have the same cardinality, $E$ is a maximal independent set of $M$. Since we made at most $|B|$ exchanges, $|B|<|A|$, and $C\cap A=\varnothing$, $E$ does not contain $A$. This is a contradiction, since we have previously determined that all independent sets of $M$ in $B^c$ must contain $A$.

Part c

Let $M=(S,\mathcal{I})$ and let $P=\{S_1,\dots ,S_k\}$ be the given partition of $S$. Clearly $\varnothing \in \mathcal{I}$ since $|\varnothing \cap S_i|=0$ for all $i$. If $A\in \mathcal{I}$ and $B\subset A$ then $|B\cap S_i|⩽|A\cap S_i|⩽1$ for all $i$, hence $B\in \mathcal{I}$. If $A,B\in \mathcal{I}$ with $|A|>|B|$ then there is an $i$ for which $|S_i\cap A|=1$ and $|S_i\cap B|=0$. Let $x\in A\cap S_i$ then $B\cup \{x\}\in \mathcal{I}$. Hence $M$ is a matroid.

---

Problem 5

$$\begin{array}{rl}& \text{BoundedDijkstra}(G(V,E),W,s\in V):\\ & \text{Initialize list }B[\mathrm{0..}W(V-1)]\text{ with }\varnothing \\ & \text{Initialize list }dist[\mathrm{1..}V]\text{ with }\infty \\ & B[0]\leftarrow s\\ & dist[s]\leftarrow 0\\ & \\ & \text{for }i\in [\mathrm{0..}W(V-1)]:\\ & \text{for }v\in B[i]:\\ & \text{for each neighbor }u\text{ of }v:\\ & dis{t}^{\prime }\leftarrow i+w(v,u)\text{\#i=dist[v]}\\ & \text{if }dist[u]>dis{t}^{\prime }:\\ & \text{remove }u\text{ from }B[dist[u]]\\ & \text{append }u\text{ to }B[dis{t}^{\prime }]\\ & dist[u]\leftarrow dis{t}^{\prime }\\ & \\ & \text{return }dist\end{array}$$

The mechanism to pick the vertex with the shortest distance has been modified to use buckets in pace of the priority queue used in the vanilla algorithm. Bounding the weights by $W$ allows us to bound maximum weight of a path in the graph by $W(V-1)$. Every vertex is processed, since a vertex can only be inserted into a later bucket or at the end of the current bucket.

Each edge is processed once, and we pass through $W(V-1)$ buckets. Thus, the algorithm runs in $O(W|V|+|E|)$ time.

---

Problem 6

Suppose $T$ is a binary tree that is not full. Then there is a node $v$ which has only one child $u$. We split the solution into two cases:

1. If $v$ is the root node then delete $v$ and use $u$ are the root node instead.
2. If $v$ is not the root node then it has a parent, say $w$. Here, delete $v$ and attach $u$ to $w$.

In both cases, we have shown that there is a new tree which uses less bits to encode the data (since we are deleting an edge). Hence $T$ cannot correspond to an optimal code.