Practicals to ADS I, summer semester 2018/19

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. To get a credit it is necessary to obtain at least two thirds ($\frac{2}{3}$ or 66.6%) of the possible points (each homework is for one point, precise number will be specified at the end of the semester, it depends on real number of seminars).

NOTE I kindly ask you to not send me scanned handwritten solutions. You can either send me your solution by e-mail (within to body, attached document), or hand me you solution on paper (handwritten, printed).

Altogether there were 10 homeworks, so the limit to get the credit is $6=\lfloor 10\frac{2}{3}\rfloor$ points. The homeworks assigned formally to the 12th practical will be considered as additional and not be counted to the limit.

Content and homework

1st practical (20th February, 2019)

  1. Overview of sorting algorithms, pseudocode of bubble-sort and its complexity.
  2. Quick-sort algorithm with complexity
  3. Binary search, pseudocode and complexity
  4. Linked list overview, implementantion of a stack and queue.

Homework

Stack is a data structure with three operations:

push(s, a)
pushes an element a to the top of stack s.
top(s)
returns the element at the top of stack s.
pop(s)
removes the element from the top of stack s.

Queue is a a data structure with three operations:

enqueue(q, a)
pushes an element a to the end of queue q.
front(q)
returns the first element of queue q.
pop(s)
removes the first element from queue q.

Assume the elements of the stack or queue are stored in an array $A$ of length $n$ (i.e. the stack or queue can contain at most $n$ elements). You may also consider other variables being part of stack or queue representation as necessary. Write pseudocode for the above operations for both stack and queue. What is the complexity of each operation in your implementation?

2nd practical (27th February, 2019)

  1. Implementation of a queue with a fixed sized array as an underlying data structure.
  2. Determine the asymptotic relation between each pair of functions \(f(n)\) and \(g(n)\) in the following table (i.e. whether \(f(n)=o(g(n))\), \(f(n)=\omega(g(n))\), or \(f(n)=\Theta(g(n))\)).
    \(\mathbf{f(n)}\)\(\mathbf{g(n)}\)
    \(n^2-30n+5\)\(0.7n^2-20n+15\)
    \(100n^3+40n^2-n\)\(0.5n^4-1000n^3\)
    \(5n^2-n\)\(30n+4\)
    \(n\)\(\sqrt{n}\)
    \(n^{\frac{3}{4}}\)\(\sqrt{n}\)
    \(\log_2 n\)\(\ln n\)
    \(n(\log_2 n)^5\)\(n\sqrt{n}\)
    \(2^n\)\(2^{2n}\)
    \(e^n\)\(2^n\)
    \(n!\)\(n^n\)
    \(n!\)\(2^n\)
    \(2^n\)\(2^{n+1}\)
  3. Consider three functions \(f_1(n)\), \(f_2(n)\), \(g(n)\) and assume \(f_1(n)=O(g(n))\) and \(f_2(n)=O(g(n))\). Is it true in general, that the following equalities hold?
    1. \(f_1(n)+f_2(n)=O(g(n))\)
    2. \(f_1(n)\cdot f_2(n)=O(g(n))\)

Homework

Consider as an input two arbitrarily long numbers described as arrays of digits 0-9, in particular given an array \(A\) of digits on indices \(0\dots n\), the array represents number \[ \sum_{i=0}^n{10}^i\cdot A[i]\text{.} \] The numbers are arbitrarily long, we cannot assume they would fit into a standard integer type. The result is again another array of digits in the same form as \(A\) and \(B\). Write a pseudocode of an algorithm which multiplies two numbers specified by arrays as above (assume that the number of digits in an array \(A\) can be obtained using \(\operatorname{len}(A)\), so above we would have \(n=\operatorname{len}(A)\)). Estimate the complexity of your algorithm.

3rd practical (6th March, 2019)

  1. Data structures for representing a graph (adjacency matrix, list of neighbours, incidence matrix, edge list)
  2. Powers of adjacency matrix
  3. Computing transitive closure of a graph by computing powers of its adjacency matrix
  4. Computing transitive closure using a BFS (or DFS)
  5. Detecting if a graph is bipartite using BFS
  6. Modify BFS so that after it finishes, we can easily reconstruct for each vertex \(i\) one of the shortest paths from the source vertex \(a\) to \(i\).
  7. Modify BFS so that it computes the number of shortest paths to each vertex.
  8. (Unfinished) Design an algorithm which for a given graph computes a closed route which uses every edge exactly twice, once in each direction.

Homework

Describe an algorithm which given an adjacency matrix $A$ of a directed graph $G=(V, E)$ finds out whether there is a vertex $v\in V$ with indegree $|V|-1$ and outdegree $0$. The algorithm should have running time $O(|V|)$.

4th practical (13th March, 2019)

  1. Revisited DFS algorithm, times of entering and leaving the vertices, classification of edges, application on an example graph.
  2. A directed graph \(G\) is singly connected if for every pair of vertices \(u\), \(v\) there is at most one path from \(u\) to \(v\) in \(G\). Give an efficient algorithm to determine whether or not a directed graph is singly connected.
  3. Recalled the definition of topological sort, the algorithm based on DFS.

Homework

Let $G=(V, E)$ be a directed graph and let $u, v\in V$ be vertices such that there is a path from $u$ to $v$ in $G$. Describe a counterexample to the following two conjectures (i.e. show that they are not true):

  1. In any DFS of $G$ we have that $d[v]\leq f[u]$.
  2. Let us fix some DFS of $G$ in which $d[u]<d[v]$, then $v$ is in a DFS subtree of $u$ (i.e. there is a path from \(u\) to \(v\) composed of tree edges).

5th practical (20th March, 2019)

  1. Describe an algorithm which given a directed acyclic graph \(G=(V, E)\) and a vertex \(s\in V\) determines the number of paths which lead to every other vertex \(v\in V\) from \(s\). Your algorithm should work in time \(O(|V|+|E|)\).
  2. We say that a directed graph \(G=(V, E)\) is half-connected if for every pair of vertices \(u, v\in V\) there is a directed path from \(u\) to \(v\) or from \(v\) to \(u\) (or both). Describe an algorithm which determines whether a given directed graph is half-connected.
  3. Find a weighted directed graph \(G=(V, E)\) with negative weights on some edges, but without cycles of negative weight, on which Dijkstra's algorithm fails.

Homework

There is no homework for this practical.

6th practical (27th March, 2019)

  1. Given an (unsorted) array \(A[1..n]\) of integers we want to check whether there is a duplicite value in the array. We want to use the following approach:
    S is a new set of integers
    for i:=1 to n do
       if S.contains(A[i])
       then
          return Duplicity(i)
       else
          S.insert(A[i])
       endif
    done
    return None
          
    What is the complexity of the above algirithm? How does it depend on implementation of the data structure representing \(S\)?
  2. Assume a directed graph \(G=(V, E)\) with weights on edges given by function \(d:E\to\mathbb{Z}\). Assume that some of the edges have negative weights and let us define \(\delta=\min_{(u, v)\in E}d(u, v)\). Let us define a new weight function as \(d'(u, v)=d(u, v)+\delta\) for every edge \((u, v)\in E\). It follows that \(d'(u, v)\geq 0\) for every edge \((u, v)\in E\). Is it possible to use Dijkstra's algorithm on \(G\) with weights \(d'\) to find shortest pathes with respect to weights \(d\)?
  3. Assume that a directed graph \(G=(V, E)\) has weights not only on edges, but on vertices as well. Describe an efficient algorithm which determines shortest paths in this case. For example: The weight on an edge \((u, v)\in E\) specifies the price of going from city \(u\) to city \(v\) by a car, the weight on a vertex \(u\) specifies the price for going through the city \(u\), e.g. a fee, we are looking for a cheapest path.
  4. Assume a directed graph \(G=(V, E)\) where vertices represent cities and edges represent roads between them. Assume that each edge \((u, v)\in E\) is associated a height \(h(u, v)\in\mathbb{N}\) of lowest profile bridge over the corresponding road. We want to find paths from a source vertex to other vertices which has the maximum lowest profile (in other words we ask how high we can load a car to safely get by it to another city). How can we modify Dijkstra's algorithm to find such a path?

Homework

Let \(G=(V, E)\) be a weighted, directed graph with nonnegative weight function \(d:E\to\{0, 1, \dots, D\}\) for some nonnegative integer \(D\) (we assume that \(D\) is reasonably small constant, e.g. \(10\)). Modify Dijkstra's algorithm to compute the shortest paths from a given source vertex \(s\) in \(O(D\cdot|V|+|E|)\) time.

Hint: Use a different implementation of a heap for storing open vertices. The suggested data structure consists of an array \(H\) where for an index \(i\) element \(H[i]\) contains a linked list of vertices at distance \(i\) from \(s\). How many items do we need to store in \(H\)? How delete_min, build_heap (or insert), decrease_key would be implemented? What would be complexity of these operations?

7th practical (3rd April, 2019)

  1. Modify Bellman-Ford's algorithm so that after it finishes, we can efficiently reconstruct shortest paths from a given source vertex \(s\) to all other vertices in a given weighted graph.
  2. How can we use Bellman-Ford's algorithm to find a negative cycle which is reachable from the source vertex?
  3. Describe an efficient algorithm which using Bellman-Ford's algorithm finds a negative cycle in a given weighted graph.
  4. Detecting negative cycles using Floyd-Warshal's algorithm.
  5. Modify Floyd-Warshal's algorithm so that it finds a shortest cycle in a given weighted graph.

Homework

Assume we are given a weighted graph \(G=(V, E)\) with weights on edges \(d:E\to\mathbb{Z}\) and no negative cycles, and vertices \(s, t\in V\). We want to find a shortest path from \(s\) to \(t\) which moreover has the minimum number of edges among all shortest paths (i.e. we are looking for a shortest path with the minimum number of transfers). Describe an efficient algorithm to solve this problem.

8th practical (10th April, 2019)

  1. Consider an undirected graph \(G=(V, E)\) with integer weights on edges \(w:E\to\mathbb{Z}\). Assume we have constructed a minimum spanning tree \(T\).
    1. Assume we decrease weight of an edge \(\{u, v\}\) which is in \(T\). Is \(T\) still a minimum spanning tree of \(G\)?
    2. Assume we decrease weight of an edge \(\{u, v\}\) which is not in \(T\). Is \(T\) still a minimum spanning tree of \(G\)? How to quickly find a minimum spanning tree of \(G\)?
    3. Assume we add a new edge \(\{u, v\}\) into \(G\). How to quickly find a minimum spanning tree of \(G\)?
    4. Assume we add a new vertex \(v\) to \(G\) together with several weighted edges connecting \(v\) to some vertices in \(G\). How to update \(T\) to obtain a minimum spanning tree of \(G\).
  2. Let us consider a graph $G=(V, E)$, a weight function $w:E\mapsto {\mathbb Z}$, and a set of vertices $S\subseteq V$, describe an algorithm, which finds a minimum spanning tree of $G$ in which all vertices of $S$ are leaves (there can be other leaves as well), or decides that there is no spanning tree with this restriction.

Homework

Let us consider the following divide-and-conquer algorithm for computing minimum spanning trees: Given a graph $G=(V, E)$, partition the set $V$ of vertices into two sets $V_1$ and $V_2$ such that $|V_1|$ and $|V_2|$ differ by at most 1. Let $E_1$ be the set of edges that are incident only on vertices in $V_1$, and let $E_2$ be the set of edges that are incident only on vertices in $V_2$. Recursively solve a minimum-spanning-tree problem on each of the two subgraphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$. Finally, select the minimum-weight edge in $E$ that crosses the cut $(V_1, V_2)$, and use this edge to unite the resulting two minimum spanning trees into a single spanning tree.

Either argue that the algorithm correctly computes a minimum spanning tree of $G$, or provide an example for which the algorithm fails.

9th practical (17th May, 2019)

  1. Write a pseudocode for operations find(t, u), max(t), min(t), pred(t), succ(t) for binary search tree t and a key u.
  2. Desribe operation print(t) which given a binary search tree t prints the keys in t in increasing order.
  3. Consider the following implementation of print(t): Find the node with minimum key in t, then repeat printing the key of current node and setting the current node to its successor while the successor is defined. Argue that the comoplexity of this algorithm is \(\Theta(n)\) where \(n\) it the number of elements in \(t\).
  4. Description of insert(t, u) and delete(t, u) in a binary search tree.
  5. Description of rotation in a binary search tree.
  6. Modify the structure of a node in a BST so that it contains pointers to the nodes with maximum and minimum elements in the subtree as well as to the successor and predecessor of the node. Show that these values can be maintained during insert, delete with the same asymptotic complexity, this is true even in balanced trees when rotations are used for balancing.

Homework

Suppose that the search for key \(k\) in a binary search tree ends up in a leaf. Consider three sets: \(A\), the keys to the left of the search path; \(B\), the keys on the search path; and \(C\), the keys to the right of the search path. Show (by giving a counterexample) that the following proposition is not true: Any \(a\in A\), \(b\in B\), and \(c\in C\) must satisfy \(a\leq b\leq c\).

10th practical (24th April, 2019)

  1. Solve the following equations using Master Theorem.
    1. $T(n)=T(\frac{7n}{10})+n$,
    2. $T(n)=16T(\frac{n}{4})+n^2$,
    3. $T(n)=7T(\frac{n}{3})n^2$,
    4. $T(n)=7T(\frac{n}{2})+n^2$,
    5. $T(n)=2T(\frac{n}{4})+\sqrt{n}$,
  2. Solve the following equations
    1. \(T(n)=T(n-1)+n\)
    2. \(T(n)=T(n-2)+n^2\)
  3. Use Master Theorem to give an upper bound and a lower bound to the function \(T(n)\) given by the following equation: \[ T(n)=4T(\frac{n}{2})+n^2\log n\]
  4. Nonrecursive implementation of merge sort
  5. Describe an algorithm which computes the number of inversions in a given permutation. The algorithm should work in time \(\Theta(n\log n)\) where \(n\) is the number of permuted integers. The permutation is given in an array.

Homework

Let us consider two arrays \(X\) and \(Y\) of \(n\) integers each. Let us assume that the arrays are sorted (say in increasing order). Describe an algorithm which finds the median of all \(2n\) numbers in both arrays. The algorithm should work in time \(O(\log n)\).

11th practical (15th May, 2019)

  1. Consider \(n\) numbers \(p_1, \dots, p_n\) with associated positive weights \(w_1, \dots, w_n\) which satisfy that \(\sum_{i=1}^n w_i=1\). We say that \(p_k\) is a weighted median of the given numbers if \(\sum_{p_i<p_k} w_i<\frac{1}{2}\) and \(\sum_{p_i>p_k} w_i\leq\frac{1}{2}\). Describe an algorithm which finds a weighted median of given numbers in time \(O(n)\). The input numbers are given in an array which is not sorted.
  2. The problem of Post office placement can be formulated as follows. We are given \(n\) points which have associated positive weights \(w_1, \dots, w_n\) satisfying \(\sum_{i=1}^n w_i=1\) and a distance function \(d(x, y)>0\) which gives a distance for any two points. We are looking for a place \(p\) for a Post office which would minimize the value of \(\sum_{i=1}^n w_i d(p, p_i)\).
    1. Argue that if \(p\in\mathbb{R}\) and \(d(x, y)=|x-y|\), then the optimal choice is \(p=p_k\) where \(p_k\) is the weighted median of \(p_1, \dots, p_n\).
    2. Assume that \(p_i\in\mathbb{R}^2\) and the distance of two points is given by Manhattan metrics, i.e. \(d(x, y)=|x_1-y_1|+|x_2-y_2|\) where \(x=(x_1, x_2)\) and \(y=(y_1, y_2)\). What is an optimal choice of \(p\) in this case?

Homework

At the input we are given $N$ screws and $N$ nuts of different sizes. For each screw there is a suitable nut. Describe an algorithm which pairs screws with their matching nuts as quickly as possible, the algorithm can only compare a screw to a nut and check if they fit together, if the screw is too big, or if the screw is too small. The algorithm cannot compare two screws or two nuts. Randomized solution with average time $O(n\log n)$ is enough.

Additional homework (in case you don't have enough points

  1. Given a directed graph $G=(V, E)$ we define a component graph $G^{SCC}=(V^{SCC}, E^{SCC})$ as follows. Suppose that $G$ has strongly connected components $C_1, \dots, C_k$. The vertex set $V^{SCC}$ is then $\{v_1, v_2, \dots, v_k\}$ (i.e. every vertex of $G^{SCC}$ corresponds to a strongly connected component of $G$) and $(v_i, v_j)\in E^{SCC}$ if $G$ contains an edge $(x, y)\in E$ for some $x\in C_i$ and $y\in C_j$. Given a directed graph $G=(V, E)$, explain how to create another graph $G'=(V, E')$ such that
    1. $G'$ has the same strongly connected components as $G$,
    2. $G'$ has the same component graph as $G$, and
    3. $E'$ is as small as possible.
    Describe a fast algorithm to compute $G'$.
  2. The diameter of an undirected tree \(T=(V, E)\) is defined as \(\max_{u, v\in V}\delta(u, v)\) where \(\delta(u, v)\) denotes the length of the path from \(u\) to \(v\) in \(T\). Thus diameter of \(T\) is the maximum length of a path in \(T\). Describe a linear time algorithm which determines the diameter of a given tree \(T\). Hint: Use BFS.
  3. Prove or disprove: If a directed graph $G$ contains cycles, then then the algorithm for topological sort based on DFS (which outputs vertices in decreasing order by their times of leave) produces a vertex ordering that minimizes the number of “bad” edges that are inconsistent with the ordering produced.