diff options
| -rw-r--r-- | src/03/01/README.md | 3 | ||||
| -rw-r--r-- | src/03/02/README.md | 4 | ||||
| -rw-r--r-- | src/03/03/README.md | 5 | ||||
| -rw-r--r-- | src/03/04/README.md | 8 | ||||
| -rw-r--r-- | src/03/05/README.md | 7 | ||||
| -rw-r--r-- | src/03/06/README.md | 3 | ||||
| -rw-r--r-- | src/03/07/README.md | 2 | ||||
| -rw-r--r-- | src/03/08/README.md | 1 |
8 files changed, 33 insertions, 0 deletions
diff --git a/src/03/01/README.md b/src/03/01/README.md new file mode 100644 index 0000000..e87168f --- /dev/null +++ b/src/03/01/README.md @@ -0,0 +1,3 @@ +Illustrate that the nodes of any AVL tree T can be +colored "red" and "black" so that T becomes a +red-black tree. diff --git a/src/03/02/README.md b/src/03/02/README.md new file mode 100644 index 0000000..eebaa47 --- /dev/null +++ b/src/03/02/README.md @@ -0,0 +1,4 @@ +Illustrate that via AVL single rotation, any binary search tree T1 can be +transformed into another search tree T2 (with the same items). + +Give an algorithm to perform this transformation using O(N log N) rotation on average. diff --git a/src/03/03/README.md b/src/03/03/README.md new file mode 100644 index 0000000..8920d5e --- /dev/null +++ b/src/03/03/README.md @@ -0,0 +1,5 @@ +Suppose you are given two sequences S1 and S2 of `n` elements, possibly +containing duplicates, on which a total order relation is defined. + +1. Describe an efficient algorithm for determining if S1 and S2 contain the same set of elements. +1. Analyze the running time of this method). diff --git a/src/03/04/README.md b/src/03/04/README.md new file mode 100644 index 0000000..0a95052 --- /dev/null +++ b/src/03/04/README.md @@ -0,0 +1,8 @@ +Given sequence 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, sort the sequence using the +following algorithms, and illustrate the details of the execution of the +algorithms: + +a. merge-sort algorithm. +b. quick-sort algorithm. + * Choose a partitioning strategy you like to pick a pivot element from the sequence. + * Analyze how different portioning strategies may impact on the performance of the sorting algorithm. diff --git a/src/03/05/README.md b/src/03/05/README.md new file mode 100644 index 0000000..c1bccdd --- /dev/null +++ b/src/03/05/README.md @@ -0,0 +1,7 @@ +Given the graph shown below, answer the following questions: + +1. Illustrate the sequence of vertices of this graph visited using depth-first search traversal starting at vertex `g`. +1. Illustrate the sequence of vertices of this graph visited using breadth-first search traversal starting at vertex `b`. +1. Illustrate adjacency list representation and adjacency matrix representation, respectively, for this graph. + * What are the advantages and disadvantages of those two representations? +1. Describe an algorithm to find in the graph a path illustrated below that goes through every edge exactly once in each direction. diff --git a/src/03/06/README.md b/src/03/06/README.md new file mode 100644 index 0000000..123d921 --- /dev/null +++ b/src/03/06/README.md @@ -0,0 +1,3 @@ +Why does the method `remove(x)` in the `RedBlackTree` implementation +perform the assignment `u:parent = w:parent?` +Shouldn’t this already be done by the call to `splice(w)`? diff --git a/src/03/07/README.md b/src/03/07/README.md new file mode 100644 index 0000000..8e85bde --- /dev/null +++ b/src/03/07/README.md @@ -0,0 +1,2 @@ +Implement the `remove(u)` method, that removes the node `u` from a +`MeldableHeap`. This method should run in `O(log n)` expected time. diff --git a/src/03/08/README.md b/src/03/08/README.md new file mode 100644 index 0000000..163f487 --- /dev/null +++ b/src/03/08/README.md @@ -0,0 +1 @@ +Prove that a binary tree with `k` leaves has height at least `log k`. |