Practicals to ADS I, summer semester 2016/17

Petr Kučera, KTIML MFF UK

Basic information

I am out of Prague on Tuesday 14th March and unfortunately I was not able to find anyone who would be willing to teach the practical instead of me. Therefore I have to cancel the practical on 14th March. I apologize for any inconvenience.

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).

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

Homeworks

1st practical (21st February, 2017)

Write a pseudocode for Euklid's algorithm for computing GCD of two numbers without using recursion.

2nd practical (28th February, 2017)

Write a pseudocode of a simple sorting algorithm (bubble sort, insertion sort, etc.) and argue about its complexity in the worst case and in the best case.

3rd practical (7th March, 2017)

Stack is 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.

Assume the elements of the stack are stored in an array $A$ of length $n$ (i.e. the stack can contain at most $n$ elements). You may also consider other variables being part of stack representation as necessary. Write pseudocode for the above three operations. What is the complexity of each operation in your implementation? There will be no homework the next week so you can submit your solution until the practical on 21st March. I will also put here a notification whether there will be practical the next week, or not (I am not in Prague most of the next week and I am still looking for someone who could teach the next week instead of me).

4th practical (14th March, 2017)

The practical was cancelled, so there was no homework.

5th practical (21th March, 2017)

Describe an algorithm which given an adjacency matrix $A$ of an 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|)$.

6th practical (28th March, 2017)

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$. Let us denote the time of entering vertex \(v\) by DFS as \(d[v]\). 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 d[u]$.
  2. Let us fix some DFS of $G$ in which $d[u]<d[v]$, then $v$ is in a DFS subtree of $u$.

7th practical (4th April, 2017)

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.

8th practical (11th April, 2017)

We are given a directed graph $G=(V, E)$ on which each edge $(u, v)\in E$ has an associated value $r(u, v)$, which is a real number in the range $O\leq r(u, v)\leq 1$ that represents the reliability of a communication channel from vertex $u$ to vertex $v$. We interpret $r(u, v)$ as the probability that the channel from $u$ to $v$ will not fail, and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.

9th practical (18th April, 2017)

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.

10th practical (25th April, 2017)

Let us consider a graph $G=(V, E)$, a weight function $w:E\mapsto {\mathbb R}$, 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.

11th practical (2nd May, 2017)

Since I did put the exercise here quite late, I extend the deadline for the submission of a solution till 16th May, 2017.

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

12th practical (9th May, 2017)

Is the operation delete in an (unbalanced) BST commutative? In particular, given a BST \(T\) and two elements \(x\) and \(y\) in the tree, is it true that removing them in order \(x, y\) and in order \(y, x\) will give us the same tree?

13th practical (16th May, 2017)

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. Hint: consider quicksort.

Additional homework

  1. 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)\).
  2. 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'$.
  3. 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.
  4. We say that a directed graph \(G=(V, E)\) is semi-connected, if for each pair of vertices \(x, y\in V\) we have that \(G\) contains a path from \(x\) to \(y\), or a path from \(y\) to \(x\) (or both). Describe a linear time algorithm which checks whether \(G\) is semi-connected.