Algorithms and Data Structures I – Practicals Summer 2017/18

Lesson Plan

• Class 1 (21 Feb)
• Class 2 (28 Feb) The Big-O notation.
• Class 3 (7 Mar) Random Access Machine.
• Class 4 (14 Mar) Breadth First Search. Homeworks:
  1. ram [12] reduced points after 11 Apr
     Implement quick sort or some $O(n \log n)$ sorting algorithm on Random Access Machine. Note: The deadline was extended by a week but your solutions are required to work on RAM simulator.
  2. paths [12] reduced points after 4 Apr
     Let $G = (V, E)$ be an undirected graph and $v, w \in V$ its vertices. Design an algorithm which calculates number of shortest paths from $v$ to $w$.
• Class 5 (21 Mar) Depth First Search.
• Class 6 (28 Mar) Connectivity in directed graphs.
• Class 7 (4 Apr) Shortest paths: Dijkstra and Bellman-Ford. Homeworks:
  1. net [12] reduced points after 25 Apr
     You have a computer network described as digraph: vertices are routers and edges are links between them. For every link you know the probability that it works. Probability that a path works is product of probabilities of its edges. How to find a path between vertices $u$ and $v$ with highest probability?
  2. 4cyc [12] reduced points after 25 Apr
     Let $G$ be a digraph and $l: E \to \mathbb R^+$ lengths of its edges. Find a shortest cycle consisting of 4 edges (running time should be better than $\Theta(n^4)$).
• Class 8 (11 Apr) Minimum Spanning Trees: Jarník, Borůvka and Kruskal.
• Class 9 (18 Apr) Binary Search Trees: Introduction. Homeworks:
  1. med [12] reduced points after 9 May
     Prove that any online algorithm that keeps median of last $k$ elements of input sequence has time complexity $\Omega(\log n)$ for adding a new element given it can only compare the input elements. (You can you that sorting $n$ elements takes $\Omega(n \log n)$ time in this model.)
  2. rebal [10 + 8] reduce points after 9 May
     Design an algorithm which makes given binary search tree perfectly balanced in linear time but it is not allowed to copy the values stored in the tree. The input tree always has $2^k - 1$ elements. Twelve points in total if it uses only $O(\log n)$ extra memory, 18 points for $O(1)$ extra memory.
• Class 10 (25 Apr) Binary Search Trees: AVL
• Class 11 (2 May) Binary Search Trees: $a,b$-trees
• Class 12 (9 May) Divide and Conquer Homeworks:
  1. wires [12]
     You have a long cable with $n$ wires on each end. You want to find for each wire on left end which wire on right end it is. All you can do is to connect and disconnect wires on left end to electricity and measure wires on right end. Moreover your algorithm must be nonadaptive which means that operations with wires must not depend on results of previously done operations (i.e. you have to make the plan for the whole process ahead of time and then execute it). We are interested only in minimizing number of operations with wires and do not care about complexity of preparing the plan and calculating the wire connections from the measurements.
• Class 13 (23 May) Amortized Complexity Homeworks:
  1. lb [12 + 4]
     Prove that any solution of [wires] problem needs $\Omega(n \log n)$ operations with wires. 12 points for non-adaptive lower bound, 4 more if your lower bound applies also to adaptive algorithms.
  2. subseq [12]
     You are given a sequence of integers $x_1,x_2,\ldots,x_n$. Find a longest consecutive subsequence such that no number repeats in it.

Credit

You need to get at least 60 points. There will be homeworks worth at least 100 points.

Send your solutions to email address husek+ads@iuuk.mff.cuni.cz, either plain text or in pdf format (using (La)TeX is recommended). Please do not use fromats like doc, docx or odt.