From 34267588e83be6ff9bb7fea0d56549cebf8d9cf7 Mon Sep 17 00:00:00 2001
From: mo khan <mo.khan@gmail.com>
Date: Sat, 26 Sep 2020 12:44:40 -0600
Subject: Add some notes on how to implement a proof

---
 src/03/07/README.md |  2 +-
 src/03/08/README.md | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 45 insertions(+), 1 deletion(-)

(limited to 'src')

diff --git a/src/03/07/README.md b/src/03/07/README.md
index 20b320e..2024b4e 100644
--- a/src/03/07/README.md
+++ b/src/03/07/README.md
@@ -1,7 +1,7 @@
+
 Implement the `remove(u)` method, that removes the node `u` from a
 `MeldableHeap`. This method should run in `O(log n)` expected time.
 
-
 ```java
 class MeldableHeap {
   Node<T> merge(Node<T> h1, Node<T> h2) {
diff --git a/src/03/08/README.md b/src/03/08/README.md
index 163f487..b2eecc3 100644
--- a/src/03/08/README.md
+++ b/src/03/08/README.md
@@ -1 +1,45 @@
+
 Prove that a binary tree with `k` leaves has height at least `log k`.
+
+```plaintext
+tree = h(k)
+assert(height(tree) == log k)
+
+for each positive natural number this is true.
+```
+
+```c
+BTree *h(int k)
+{
+  BTree *tree = rb_tree_initialize();
+  // assert(true == true);
+  // generate k leaves with random data
+  return tree;
+}
+
+for (int k = 0; k < 1000; k++) {
+  assert(height(h(k)) >= log(k))
+}
+```
+
+
+```plaintext
+n: 3
+h: 3
+
+(x)
+  \
+  (y)
+    \
+    (z)
+
+n: 3
+k: 2
+h: 2
+
+    (y)
+   /   \
+(x)     (z)
+
+2^x == 2
+```
-- 
cgit v1.2.3