diff options
| author | mo khan <mo.khan@gmail.com> | 2020-07-11 15:46:37 -0600 |
|---|---|---|
| committer | mo khan <mo.khan@gmail.com> | 2020-07-11 15:46:37 -0600 |
| commit | 1efedbdd9f040810ebe7ff63f736e863c36ac82a (patch) | |
| tree | 3abf7b9999d4431415d587a3ea379fad15ff6422 | |
| parent | 7875e6df22f74499a6d756a87740f2c27cbf081a (diff) | |
Start assignment 2
| -rw-r--r-- | src/02/01/README.md | 4 | ||||
| -rw-r--r-- | src/02/02/README.md | 1 | ||||
| -rw-r--r-- | src/02/03/README.md | 3 | ||||
| -rw-r--r-- | src/02/04/README.md | 5 | ||||
| -rw-r--r-- | src/02/05/README.md | 3 |
5 files changed, 16 insertions, 0 deletions
diff --git a/src/02/01/README.md b/src/02/01/README.md new file mode 100644 index 0000000..2a36c6b --- /dev/null +++ b/src/02/01/README.md @@ -0,0 +1,4 @@ +Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation: +* preorderNext(x): return the node visited after node x in a pre-order traversal of BT. +* postorderNext(x): return the node visited after node x in a post-order traversal of BT. +* inorderNext(x): return the node visited after node x in an in-order traversal of BT. diff --git a/src/02/02/README.md b/src/02/02/README.md new file mode 100644 index 0000000..16cd9c1 --- /dev/null +++ b/src/02/02/README.md @@ -0,0 +1 @@ +Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node. diff --git a/src/02/03/README.md b/src/02/03/README.md new file mode 100644 index 0000000..b3f46e0 --- /dev/null +++ b/src/02/03/README.md @@ -0,0 +1,3 @@ +Illustrate what happens when the sequence 1, 5, 2, 4, 3 is added to an empty +ScapegoatTree, and show where the credits described in the proof of Lemma 8.3 go, +and how they are used during this sequence of additions. diff --git a/src/02/04/README.md b/src/02/04/README.md new file mode 100644 index 0000000..235f0a6 --- /dev/null +++ b/src/02/04/README.md @@ -0,0 +1,5 @@ +Implement a commonly used hash table in a program that handles collision using linear probing. + +Using (K mod 13) as the hash function, store the following elements in the table: + +{1, 5, 21, 26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146}. diff --git a/src/02/05/README.md b/src/02/05/README.md new file mode 100644 index 0000000..e1ad8da --- /dev/null +++ b/src/02/05/README.md @@ -0,0 +1,3 @@ +Create a subclass of `BinaryTree` whose nodes have fields for storing preorder, post-order, and in-order numbers. +Write methods `preOrderNumber()`, `inOrderNumber()`, and `postOrderNumbers()` that assign these numbers correctly. +These methods should each run in `O(n)` time. |