Practical to ADS II, winter semester 2019/20

Petr Kučera, KTIML MFF UK

(Česká verze)

Basic information

Credit requirements

At the end of each practical a homework will be assigned. I will expect its solution until the beginning of the next practical. 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 practicals).

There were $10$ homework assignments, so the necessary number of points for the credit is strictly more than $6.5$.

Content and homework

1st practical (3rd October, 2019)

  1. Naïve string matching algorithm and its complexity.
  2. Assume that there is no character which would occur twice within the pattern string. Modify the naïve string matching algorithm which using this assumption achieves linear time complexity of the search.
  3. Suppose that pattern \(P\) and text \(T\) are randomly chosen strings of length \(m\) and \(n\), respectively, from the \(d\)-ary alphabet \(\Sigma_d=\{0, 1, \dots, d-1\}\), where \(d\geq 2\). Show that the expected number of character-to-character comparisons made by the naïve string matching algorithm is \[ (n-m+1)\frac{1-d^{-m}}{1-d^{-1}}\leq 2(n-m+1) \] where \(m\) denotes the length of the pattern \(P\) and \(n\) denotes the length of the text \(T\).
  4. Describe an algorithm which checks if a string \(A\) is a cyclic shift of a string \(B\). The algorithm should run in linear time provided we have a linear time string matching algorithm.
  5. Describe an algorithm which given a string \(A\) and an \(0\leq k\leq |A|\) shifts \(A\) cyclically by \(k\) positions. The algorithm should work in linear time \(O(n)\) where \(n\) denotes the length of \(A\) and should only use \(O(1)\) bytes of additional memory.

Homework

Suppose we allow the pattern $P$ to contain occurrences of a gap character * that can match an arbitrary string of characters (including an empty string). For example, the pattern $P=$ ab*ba*c occurs in the text $T=$ cabccbacbacab as ab[cc]ba[cba]c and as ab[ccbac]ba[]c (the square brackets contain the string matching the gap character *). Note that the gap character may occur an arbitrary number of times in the pattern but not at all in the text. Give a polynomial-time algorithm to determine whether such a pattern $P$ occurs in a given text $T$, and analyze the running time of your algorithm.

2nd practical (10th October, 2019)

  1. Described Trie data structure.
  2. We have a text split into words. Describe an efficient algorithm which counts the number of occurrences of each word in the text.
  3. 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.
  4. Described the search automaton and its application to find occurrences of a set of patterns in a text.
  5. We are given a set of patterns \(P_1, \dots, P_k\) and a text \(T\). We want to count for each pattern how many times does it occur in the text as a substring. Assume we have built a search automaton for the patterns \(P_1, \dots, P_k\). Describe an algorithm which counts the occurrences of the patterns in time \(O(n)\) where \(n\) is the length of the text.

Homework

Describe an algorithm which finds a longest common substring of two given strings.

3rd practical (17th October, 2019)

  1. Demonstrated Aho-Corasick algorithm on the set of patterns: hello, helen, length, hand, and, land.
  2. Described Knuth-Morris-Pratt algorithm and its differences from the Aho-Corasick algorithm. Demonstrated the prefix function on an example string ababbabbabbababbabb.

Homework

Let \(y^i\) denote the concatenation of string \(y\) with itself \(i\) times. For example, \((ab)^3=ababab\). We say that a string \(x\in\Sigma^*\) has repetition factor \(r\) if \(x=y^r\) for some string \(y\in\Sigma^*\) and some \(r>0\). Let \(\rho(x)\) denote the largest \(r\) such that \(x\) has repetition factor \(r\). Give an efficient algorithm that takes as input a patterh \(P[1\dots m]\) and computes the value \(\rho(P_i)\) for \(i=1, ..., m\) where \(P_i\) denotes the prefix of \(P\) of lentgh \(i\).

4th practical (24th October, 2019)

  1. Modify Rabin-Karp algorithm to search for a matrix \(P\) of size \(m\times m\) within a matrix \(T\) of size \(n\times n\).
  2. Find maximum matching in a bipartite graph using an algorithm for finding a maximum flow in a network.

Homework

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 practical (31st October, 2019)

  1. How to find a minimum cut in a network given a maximum flow.
  2. Find a minimum vertex cover of a bipartite graph by finding a minimum cut in a suitable network.
  3. Given two vertices \(s\) and \(t\) in an undirected graph \(G\), determine a maximum set of pairwise edge-disjoint paths from \(s\) to \(t\) in \(G\).
  4. Given an undirected graph \(G\), determine the maximum value of \(k\) for which \(G\) is edge \(k\)-connected.
  5. Assume that we also assign capacities to vertices in a network, describe an algorithm to find a maximum flow in such a modified network (reduce the problem to finding a maximum flow in a network with capacities only on edges).
  6. Given an undirected graph \(G\), determine the maximum value of \(k\) for which \(G\) is vertex \(k\)-connected.
  7. 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?

Homework

Let us have projects \(P_1, \dots, P_k\) and resources \(S\). To complete a project \(P_i\) we need resources \(S_i\subseteq S\), each resource \(s_j\in S\) costs us \(c_j\), but once purchased it can be reused in several projects. We get a reward \(r_i\) for finishing project \(P_i\). Describe an algorithm which decides which projects should be completed and which resources should be purchased to maximize the profit. Hint: Use the problem of finding a minimum cut in a suitable network.

6th practical (7th November, 2019)

  1. Simulation of Dinic algorithm on an example graph.
  2. 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.

Homework

Suppose that you wish to find, among all minimum cuts in a flow network $G$, one that contains the smallest number of edges. Show how to modify the capacities of $G$ to create a new flow network $G'$ in which any minimum cut in $G'$ is a minimum cut with the smallest number of edges in $G$.

7th practical (14th Norember, 2019)

  1. Simulation of the Goldberg (Preflow-Push) algorithm on a path on five vertices with capacities all ones and then with decreasing capacities (4-3-2-1).
  2. Notes on implementation of the Goldberg algorithm.

Homework

Recall that the running time of Dinic algorithm is \(O(n^2 m)\) where \(n\) denotes the number of vertices and \(m\) denotes the number of edges of the network. Describe a network on which Dinic algorithms requires time \(\Omega(n^2 m)\). In particular, describe a network, on which Dinic algorithm performs \(\Omega(n)\) phases (in which a level network is constructed) and for each of these level network Dinic algorithm spends \(\Omega(nm)\) time to find a blocking flow.

8th practical (28th November, 2019)

  1. Recollected the FFT algorithm.
  2. Description of using Fourier transformation for signal processing.
  3. 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$.)

Homework

Given a list of values \(z_0, z_1, ..., z_{n-1}\) (possibly with repetitions), show how to find the coefficients of a polynomial \(P(x)\) of degree-bound \(n+1\) that has zeros only at \(z_0, z_1, ..., z_{n-1}\) (possibly with repetitions). Your procedure should run in time \(O(n\log^2 n)\). (Hint: The polynomial \(P(x)\) has a zero at \(z_j\) if and only if \(P(x)\) is a multiple of \((x-z_j)\).)

9th practical (5th December, 2019)

  1. Design a network of comparators which computes the maximum of the given \(n\) numbers. In particular, the network shall have \(n\) inputs \(x_1, \dots, x_n\) and \(n\) outputs \(y_1, \dots, y_n\) such that \(y_n=\max_{i=1}^n x_i\). The depth of this network should be \(O(\log n)\).
  2. Design a network of comparators which inserts an element into a sorted sequence. In particular, the network shall have \(n\) inputs \(x_1, \dots, x_n\) and \(n\) outputs \(y_1, \dots, y_n\). Assuming that \(x_1<x_2<\dots<x_{n-1}\) the outputs should satisfy \(y_1<\dots< y_{n-1}<y_n\). The depth of this network should be \(O(\log n)\).
  3. Design a network of comparators which sorts a fixed permutation of numbers (we do not care about the behaviour of the network when a different permutation is presented to its inputs). The depth of this network should be \(O(\log n)\).
  4. Described Batcher's merge sorting network with an example on 8 inputs.
  5. Described bitonic merge sorting network with an example on 8 inputs.

Homework

We can represent an $n$-input comparator 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 (sequential) algorithm for determining the depth of a comparison network.

10th practical (12th December, 2019)

  1. Design a circuit of depth \(\log_2 n\) which computes a disjunction of \(n\) bits.
  2. Recollection of the carry-lookahead algorithm.
  3. Design a circuit of depth \(O(\log_2 n)\) which compares two \(n\)-bit numbers (with result \(<\), \(=\), or \(>\)).
  4. Describe a circuit of constant depth which given three \(n\)-bit numbers \(s_1\), \(s_2\), \(s_3\) returns two \(n\)-bit numbers \(t_1\) and \(t_2\) such that \(t_1+t_2=s_1+s_2+s_3\). Use the circuit to show that there is a circuit for computing the product of two \(n\)-bit numbers of depth \(O(\log_2 n)\).

Homework

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_2 n\).

Additional homework

  1. 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.
  2. 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.
  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\). 1 point for any circuit, 2 points for a circuit of depth \(\Theta(\log_2 n)\).
  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.
  5. Assume we have a chessboard \(B\) of size \(n\times n\) which has holes in it (some cells are not there). We want to cover the remaining cells with dominoes of size \(1\times 2\). Design an efficient algorithm which finds out if it is possible and if so, it finds a particular way of how to do it. (Hint: formulate as a flow problem.)
  6. We have a map of Manhattan: a square grid, line crossings represent crossroads, lines between represent streets and avenues, some of them cannot be driven through due to congestion (thus the map is an incomplete square grid). A car has broken in one of the streets and now it only can drive straight and turn right. It needs to get to a repair shop. Find a shortest route for the car to the repair shop (at a specified crossroad).
  7. Describe an efficient algorithm which given a directed graph, finds a node from which all other nodes are reachable by a path (or answers no if no such node exists). Should work in linear time \(O(|E|+|V|)\).
Petr Kučera <>