Seminar to ADS II, winter semester 2017/18

Petr Kučera, KTIML MFF UK

Basic information

Credit requirements

At the end of each seminar a homework will be assigned. I will expect its solution until the beginning of the next seminar. You can either send me your solution by e-mail, or hand it to me on paper at the beginning of the next practical. In case you use e-mail, then I would like to ask you to either write the solution to the message body, or attach a document which is produced using an editor. Please, do not send me a scanned handwritten solution (you can draw and scan a picture if needed, however the text should be written on a computer). You can give me your handwritten solution during practical.

To get a credit it is necessary to obtain at least two thirds of the possible points (each homework is for one point, precise number will be specified at the end of the semester, it depends on the real number of seminars).

I will count the first 11 homework assignments into the limit. Homework to the last practical will be considered as additional for those who do not have enough points. It means that the necessary number of points is $\frac{2\cdot 11}{3}=7\frac{1}{3}$.

Homework

1st practical (3rd October, 2017)

Design a data structure which stores a dictionary of words. Given a word $w$, the the data structure is then used to quickly find the best rhyme, i.e. the word $w'$ in the dictionary which has a longest commong suffix with $w$. If there are more choices, then the lexicographically first such rhyme should be returned. Consider trie we described during practical.

2nd practical (10th October, 2017)

Let us denote $f(i)$ the backwards (or prefix) function for pattern $P$ from KMP algorithm. Let $f^*(i)=\{f(i), f^{(2)}(i), f^{(3)}(i), ..., f^{(t)}(i)\}$ where \(f^{(k)}(i)\) is $f(i)$ iterated $k$-times and $t$ is the smallest number satisfying $f^{(t)}(i)=0$. Show that $f^*(i)=\{k\mid k \lt i\text{ and $P[0:k]$ is a suffix of $P[0:i]$}\}$. Show an upper bound on the size of $f^*(i)$ and show on an example that your upper bound is tight.

3rd seminar (17th October, 2017)

Aho-Corrasick algorithm Construct a search automaton (i.e. its transition function, failure function and output function) for the following set of strings: machine, marble, mars, lend, end, arthur

4th practical (24th October, 2017)

Assume we have a chessboard $B$ of size $n\times n$, which has holes in it (some cells are not there). We want to put as many rooks as possible so that they cannot capture each other. The rooks cannot be placed in holes, but can jump over them when capturing another rook. Describe how to solve this problem using a network flow algorithm. Hint: Reformulate it as finding a maximum matching in a bipartite graph.

5th seminar (31st October, 2017)

We have a set of factories $F_1, \dots, F_p$ and a set of stores $S_1, \dots, S_q$, all the factories and stores produce and sell the same type of product. Factory $F_i$, $i=1, \dots, p$ is able to produce $a_i$ units of the product each day and a store $S_j$, $j=1, \dots, q$ sells $b_j$ units each day. We have a bipartite graph which specifies from which factory to which store we can transport the product. How can we check whether the store demands can be satisfied? How to determine from which factory to which store and how much of the product should we transport each day?

6th practical (7th November, 2017)

Let $G = (V, E)$ be a flow network with source $s$, sink $t$, and integer capacities. Suppose that we are given a maximum flow in $G$.

  1. Suppose that the capacity of a single edge $(u, v)\in E$ is increased by 1. Give an $O(V + E)$-time algorithm to update the maximum flow.
  2. Suppose that the capacity of a single edge $(u, v)\in E$ is decreased by 1. Give an $O(V + E)$-time algorithm to update the maximum flow.

7th practical (14th November, 2017)

The depth of a circuit is defined as the maximum number of gates on any path from an input to the output. Using associativity of disjunction, it is not hard to describe a circuit for function \((x_1\lor x_2\lor\cdots\lor x_n)\) (i.e. \(n\)-bit disjunction) whose depth is \(\log_2 n\). Show that any circuit (in which gates have at most 2 inputs) computing \(n\)-bit disjunction requires depth at least \(\log n\).

8th practical (28th November, 2017)

Design a network of comparators which computes maximum and minimum of \(n\) numbers \(x_1, \ldots, x_n\). In particular, the network shall have \(n\) inputs \(x_1, \ldots, x_n\) and \(n\) outputs \(y_1, \ldots, y_n\). The outputs satisfy that \(y_1=\min_{i=1}^n x_i\) and \(y_n=\max_{i=1}^n x_i\). The depth of this network should be \(O(\log n)\).

9th practical (5th December, 2017)

We can represent an $n$-input comparison network with $c$ comparators as a list of $c$ pairs of integers in the range from $1$ to $n$. If two pairs contain an integer in common, the order of the corresponding comparators in the network is determined by the order of the pairs in the list. Given this representation, describe an $O(n + c)$-time (serial) algorithm for determining the depth of a comparison network.

10th practical (12th December, 2017)

Consider two sets $A$ and $B$, each having $n$ integers in the range from $0$ to $10n$. We wish to compute the Cartesian sum of $A$ and $B$, defined by \[C=\{x+y\mid x\in A\mbox{ and }y\in B\}\mbox{ .}\] Note that the integers in $C$ are in the range from $0$ to $20n$. We want to find the elements of $C$ and the number of times each element of $C$ is realized as a sum of elements in $A$ and $B$. Show how to solve the problem in $O(n\log n)$ time. (Hint: Represent $A$ and $B$ as polynomials of degree at most $10n$.)

11th practical (19th December, 2017)

Let us define the problems of Vertex Cover and Binary Integer Programming as follows:

Vertex cover
Instance: Graph $G=(V, E)$ and a natural number $k\geq 0$.
Question: Is there a set of vertices $S\subseteq V$ of size at most $k$ such that each edge $\{u, v\}\in E$ has at least one endpoint in $S$ (i.e. $u\in S$ or $v\in S$)?
Binary Integer programming (BIP)
Instance: An integer valued matrix $A$ of type $m\times n$ and an integer valued vector of length $m$.
Question: Is there a $\{0,1\}$ valued vector $x$ of length $n$ such that $Ax\geq b$?

Show that Vertex Cover is polynomial-time reducible to Binary Integer programming.

Additional homework

  1. Describe an effective algorithm for the following task: Given a set of points in plane, determine a rectangle with the smallest possible perimeter which contains all the points. The rectangle is not necessarily aligned with \(x\) or \(y\) axis.
  2. We have projects \(P_1, \ldots, P_k\) and a set of resources \(T_1, \ldots, T_q\). Finishing a project \(P_i\) is rewarded by amount \(r_i\), but we need a set of resources \(S_i\). Each resource \(T_j\) costs \(c_j\), but once it is bought, we can use it in as many projects as we want. Design an algorithm which projects should be realized and which resources should be bought to maximize the total reward. Hint: Consider this as a task of finding a minimum cut in a network. You want to minimize the total cost of resources and rewards for projects which were not finished. It is related to the homework with factories above.
  3. Design a circuit which given an \(n\)-bit number \(x\) computes \(\lfloor \log_2 x\rfloor\). This is equal to the maximum significant bit which is \(1\).
  4. Let us define a Fibonacci string as follows: \(F_0=\mathtt{a}\), \(F_1=\mathtt{b}\), \(F_{n+2}=F_nF_{n+1}\). Describe an algorithm which finds a longest Fibonacci substring in a given string.